うーん、これは典型っぽいな…。
https://community.topcoder.com/stat?c=problem_statement&pm=15228
問題
文字列集合Sと、文字列Tが与えられる。
Sを等確率でランダム順に並べて連結してできる文字列において、Tが部分列として登場する回数の期待値を求めよ。
解法
dp(0,0)から初めて、以下を順次求めていこう。
dp(mask,s) := Sのうちmaskに示す要素を並べてできた文字列のうち、最大でsuffix s文字とTのprefix s文字が一致するような状態になる確率
dp(mask,s)に対し、maskに未登場の文字列をSから当確率で選び、どう状態遷移するかをKMP法の要領で求めていけばよい。
int N,L; double dp[1<<15][55]; int table[16][55]; int num[16][55]; string S; class RandomConcat { public: void create_table(int id,string T) { for(int cur=0;cur<=S.size();cur++) { string U=S.substr(0,cur); FORR(t,T) { U+=t; while(U.size()>S.size()) U.erase(U.begin()); while(U!=S.substr(0,U.size())) U.erase(U.begin()); if(U.size()==S.size()) num[id][cur]++; } table[id][cur]=U.size(); } } double expectation(vector <string> pieces, string needle) { N=pieces.size(); S=needle; int i,j; ZERO(table); ZERO(num); FOR(i,N) create_table(i,pieces[i]); double ret=0; ZERO(dp); dp[(1<<N)-1][0]=1; for(int mask=(1<<N)-1;mask>0;mask--) { FOR(i,S.size()+1) if(dp[mask][i]>0) { double cand=dp[mask][i]/__builtin_popcount(mask); FOR(j,N) if(mask&(1<<j)) { ret+=cand*num[j][i]; dp[mask^(1<<j)][table[j][i]]+=cand; } } } return ret; } }
まとめ
Codeforcesっぽい。