kmjp's blog

競技プログラミング参加記です

TopCoder SRM 686 Div1 Medium CyclesNumber

ちょっと難しすぎないですかね…。
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種スターリング数とすると、求めたいのは \displaystyle \sum_{k=1}^N \left(s(N,k) k^M\right)である。
ただ、s(N,N)を求めるのはO(N^2)かかるため、これをそのまま求めてはTLEする。

スターリング数 - Wikipedia
上記記事を見ると、 k^M = \sum_{i=0}^M \left( S(N,i) {}_k P_i\right)と変形できることがわかる。(S(n,m)は第2種スターリング数)
すると元の式は \displaystyle \sum_{k=1}^N \left(s(N,k) k^M\right) = \sum_{k=1}^N \left(s(N,k) \sum_{i=0}^M \left( S(N,i) {}_k P_i\right)\right)となる。
S(N,i)の部分はkを含まないので総和の取る順を並べ替えて \displaystyle \sum_{i=0}^M \left( S(N,i) \left( \sum_{k=1}^N \left(s(N,k) {}_k P_i\right)\right)\right)となる。

S(N,M)を求めるのはO(NM)かかるが、幸いMはNより小さいのでこちらはなんとか間に合う。
あとはS(N,i)に続く部分を求めることを考える。
この状態ではまだs(N,k)の部分が最大O(N^2)かかりTLEする。

ここで上記Codeforcesコメントのようにマクローリン展開を用いて式変形すると(すいません、この部分追い切れていません)
 \displaystyle \sum_{k=1}^N \left(s(N,k) {}_k P_i\right) = s(N+1,i+1) i!となる。
s(N+1,i+1)はiの上限がMなのでO(NM)で済み、こちらはなんとか列挙できる。

まとめると、s(n,m)及びS(n,m)をn≦100001、m≦301の範囲で求めておき、 \displaystyle \sum_{i=0}^M \left(s(N+1,i+1) i!\right)を求めればよい。

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相当じゃないかと言ってる人も。