yukicoder : No.8048 Order and Harmony

ネタ問題？
https://yukicoder.me/problems/no/8048

問題

整数列Xに対し、X[s,t)とは、X[s],X[s+1]....,X[t-1]を指す。なお、indexは|X|を超えてもよいが、その時は|X|で割った余りのindexと同じ要素を指すものとする。
整数列Xが令和であるとは、Xの総和が0であることを意味する。
また、あるX[s,t)がonly oneであるとは、x＜tかつX[s,x)が令和となるものが無いものをいう。

正整数Kが与えられる。
K要素の整数列Aのうち以下を満たすのは何通りか。

• 各要素は1か-1である。
• 0≦L＜Kに対し、L＜RのうちA[L,R)がonly oneなのはK通り

解法

Aのうち1,-1が半数ずつあれば条件を満たす。
Kが奇数の時は解なし。
Kが偶数の時は二項係数を求めるだけだが、Kが大きいので埋め込みを併用しよう。

const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll fact(ll v) {
	static int data[][2]= {
		{0,1},
		{10000000,682498929},
		{20000000,491101308},
		{30000000,76479948},
		{40000000,723816384},
		{50000000,67347853},
		{60000000,27368307},
		{70000000,625544428},
		(略)
		{970000000,492741665},
		{980000000,377329025},
		{990000000,847549272},
		{1000000000,698611116},
		{1010000000,0},
	};
	if(v>=mo) return 0;
	int cur=v/10000000*10000000;
	ll ret=data[cur/10000000][1];
	for(int i=cur+1;i<=v;i++) ret=ret*i%mo;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;

	int N;
	cin>>N;
	if(N%2) {
		cout<<0<<endl;
	}
	else {
		cout<<fact(N)*modpow(fact(N/2))%mo*modpow(fact(N/2))%mo<<endl;
	}
}

まとめ

カテゴリ的には教育的問題に入ってるんだな。