TopCoder SRM 848 : Div1 Easy Div2 Hard AlternateParity

また平日午前回なので参加できず。
https://community.topcoder.com/stat?c=problem_statement&pm=18085

問題

正整数N,Lが与えられる。
以下を満たす整数列は何通りか。

• 1～Nの値を取るL要素の数列である
• 単調増加である
• 隣接要素の偶奇は一致してはならない

解法

先頭要素xを総当たりしよう。
それ以降(N-x)要素から残り(L-1)要素を選ぶことになる。
偶奇が一致しないということは、選ばない(N-x)-(L-1)要素は、末尾を除けば偶数個単位で区切られていなければならない。
逆に先に2要素ずつ組にしておけば重複組み合わせで計算できる。

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

class AlternateParity {
	public:
	int count(int N, int L) {
		
		ll ret=0;
		for(int i=1;i<=N;i++) if(i+L-1<=N) {
			int lef=(N-i-(L-1))/2;
			ret+=hcomb(L,lef);
		}
		
		return ret%mo;
		
	}
}

まとめ

結構シンプル。