TopCoder SRM 852 : Div1 Hard RepeatedApplication

これは割とすんなりだった。
https://community.topcoder.com/stat?c=problem_statement&pm=18164

問題

0～(N-1)の整数xを受け取り、0～(N-1)を返す関数f(x)を考える。
これは入出力の組み合わせがN^N通りある。
このうち以下を満たすのは何通りか。

• xにfをK回適用すると、N-1-xになる。

解法

Nが奇数の時、f((N-1)/2)=(N-1)/2であることが必須なので、残りの要素を考えると、Nが偶数の時だけ考えればよい。
fは何らかの置換になるので、N頂点のfunction graphを考える。
その中でもし長さ2Lの閉路があり、かつK % 2L = Lであれば、xのL個先にN-1-xが来るようなグラフを組むことで条件を満たせる。
よって、N頂点を、そのような長さ2Lの閉路の集まりとなるようにしよう。
あとはDPで、残された頂点群のうち最小番号を含む閉路の長さを総当たりしていくとよい。

const ll mo=1000000007;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
static ll fact2[NUM_+1];
ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll dp[2020];

class RepeatedApplication {
	public:
	int count(int N, int K) {
		N/=2;
		
		int i,j;
		inv[1]=fact[0]=factr[0]=fact2[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo, fact2[i]=fact2[i-1]*i*2%mo;
		
		ZERO(dp);
		dp[N]=1;
		for(i=N;i>=1;i--) {
			for(j=1;j<=i;j++) {
				if(K%(2*j)==j) (dp[i-j]+=dp[i]*comb(i-1,j-1)%mo*fact2[j-1])%=mo;
			}
		}
		return dp[0];
		
	}
}

まとめ

Mediumを落としたけど、Hardがすんなり解けたおかげでHighest更新できた。