ちょっと難しすぎないですかね…。
https://community.topcoder.com/stat?c=problem_statement&pm=14199
問題
置換列Pと整数Mに対するf(P,M)をPにおけるサイクルの数をkとしたときk^Mとして定義する。
整数N,Mが与えられる。
N要素の全ての置換列Pにおけるf(P,M)の和を求めよ。
なお、N,Mの対は最大300個与えられる。
解法
とても自力では解けないので以下の内容を見て回答。
Topcoder Single Round Match 686 - Codeforces
s(n,m)を第1種スターリング数とすると、求めたいのはである。
ただ、s(N,N)を求めるのはO(N^2)かかるため、これをそのまま求めてはTLEする。
スターリング数 - Wikipedia
上記記事を見ると、と変形できることがわかる。(S(n,m)は第2種スターリング数)
すると元の式はとなる。
S(N,i)の部分はkを含まないので総和の取る順を並べ替えてとなる。
S(N,M)を求めるのはO(NM)かかるが、幸いMはNより小さいのでこちらはなんとか間に合う。
あとはS(N,i)に続く部分を求めることを考える。
この状態ではまだs(N,k)の部分が最大O(N^2)かかりTLEする。
ここで上記Codeforcesコメントのようにマクローリン展開を用いて式変形すると(すいません、この部分追い切れていません)
となる。
s(N+1,i+1)はiの上限がMなのでO(NM)で済み、こちらはなんとか列挙できる。
まとめると、s(n,m)及びS(n,m)をn≦100001、m≦301の範囲で求めておき、を求めればよい。
ll mo=1000000007; int S1[101010][303]; int S2[101010][303]; ll fact[101010]; class CyclesNumber { public: vector <int> getExpectation(vector <int> n, vector <int> m) { int i,x,y; fact[0]=1; for(i=1;i<=100001;i++) fact[i]=fact[i-1]*i%mo; for(i=0;i<=100001;i++) { for(x=1;x<=min(i,301);x++) { S1[i][x] = (S1[i-1][x-1] + 1LL*(i-1)*S1[i-1][x])%mo; S2[i][x] = (S2[i-1][x-1] + 1LL*x*S2[i-1][x])%mo; } if(i<=301) S1[i][i]=S2[i][i]=1; } vector<int> V; FOR(i,n.size()) { ll ret=0; for(int c=0;c<=m[i];c++) ret += 1LL*S2[m[i]][c] * S1[n[i]+1][c+1] % mo * fact[c] % mo; V.push_back(ret%mo); } return V; } }
まとめ
マクローリン展開前後の式変形難易度高すぎじゃないですかね…。
実際Codeforcesの上記エントリではCFで赤コーダー相当の人もこれは無茶だと言っているし、Div1 Hard相当じゃないかと言ってる人も。