Codeforces #1045 : Div2. F. Permutation Oddness

なるほど。
https://codeforces.com/contest/2134/problem/F

問題

整数C0,C1,C2,C3が与えられる。
N=C0+C1+C2+C3とし、整数列Bを考える。この時、B中の0,1,2,3の頻度はC0,C1,C2,C3であるものとする。

f(B)を、隣接要素のlowbitの総和とする。
f(B)の値は0～2*(N-1)のいずれかとなる。あり得るBの組み合わせに対し、f(B)の値が0,1,2...,2*(N-1)となるのは何通りか。

解法

Bの各要素を、

• 0,2となるものは青
• 1,3となるものは赤

とする。青と赤の境界では、lowbit値は1となる。
青同士・赤同士が隣接するところでは、lowbit値は0か2となる。
よってそれぞれを求めよう。

青と赤の塊の数を定めれば、lowbitが1となる箇所はわかる。
その際生じる青同士・赤同士の隣接箇所の数に応じ、0,2や1,3の割り振りに寄りlowbitが2となるケースの個数を数え上げよう。

int T,C0,C1,C2,C3;
const ll mo=1000000007;

ll from[808][808][2];
ll to[808][808][2];

ll P02[808][808];
ll P13[808][808];
ll ret[1808];

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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int a,b;
	
	cin>>T;
	while(T--) {
		cin>>C0>>C1>>C2>>C3;
		
		if(C0>C2) swap(C0,C2);
		if(C1>C3) swap(C1,C3);
		
		ZERO(P02);
		ZERO(P13);
		
		ZERO(from);
		from[0][0][0]=from[1][0][1]=1;
		for(i=1;i<C0+C2;i++) {
			ZERO(to);
			FOR(x,min(C0,i)+1) FOR(y,min(i,C0*2)+1) {
				(to[x][y+1][0]+=from[x][y][1]);
				(to[x+1][y+1][1]+=from[x][y][0]);
				(to[x][y][0]+=from[x][y][0]);
				(to[x+1][y][1]+=from[x][y][1]);
			}
			FOR(x,min(C0,i)+2) FOR(y,min(i,C0*2)+2) {
				from[x][y][0]=to[x][y][0]%mo;
				from[x][y][1]=to[x][y][1]%mo;
			}
		}
		
		//分割
		for(i=1;i<=C0+C2;i++) {
			FOR(j,C0+C2) {
				ll p=from[C0][j][0]+from[C0][j][1];
				k=C0+C2-1-j;
				// jからa個、kからb個分割。a点減る
				for(int a=0;p&&a<=j;a++) {
					int b=i-1-a;
					if(b>=0&&b<=k) (P02[i][j-a]+=p*comb(j,a)%mo*comb(k,b))%=mo;
				}
			}
		}
		
		
		ZERO(from);
		from[0][0][0]=from[1][0][1]=1;
		for(i=1;i<C1+C3;i++) {
			ZERO(to);
			FOR(x,min(C1,i)+1) FOR(y,min(i,C1*2)+1) {
				(to[x][y+1][0]+=from[x][y][1]);
				(to[x+1][y+1][1]+=from[x][y][0]);
				(to[x][y][0]+=from[x][y][0]);
				(to[x+1][y][1]+=from[x][y][1]);
			}
			FOR(x,min(C1,i)+2) FOR(y,min(i,C1*2)+2) {
				from[x][y][0]=to[x][y][0]%mo;
				from[x][y][1]=to[x][y][1]%mo;
			}
		}
		
		//分割
		for(i=1;i<=C1+C3;i++) {
			FOR(j,C1+C3) {
				ll p=from[C1][j][0]+from[C1][j][1];
				k=C1+C3-1-j; 
				
				// jからa個、kからb個分割。a点減る
				for(int a=0;p&&a<=j;a++) {
					int b=i-1-a;
					if(b>=0&&b<=k) (P13[i][j-a]+=p*comb(j,a)%mo*comb(k,b))%=mo;
				}
			}
		}


		ZERO(ret);
		for(int p02=1;p02<=C0+C2;p02++) {
			for(int p13=max(1,p02-1);p13<=min(C1+C3,p02+1);p13++) {
				FOR(a,C0+C2) FOR(b,C1+C3) {
					ll c=P02[p02][a]*P13[p13][b]%mo;
					if(p02==p13) (c*=2)%=mo;
					int add=(p02==p13)?(2*p02-1):min(p02,p13)*2;
					(ret[a*2+b*2+add]+=c)%=mo;
				}
			}
		}
		FOR(i,2*(C0+C1+C2+C3)-1) cout<<ret[i]<<" ";
		cout<<endl;
		
		
	}
}

まとめ

もう少し時間があれば思いついたかもしれないが、Eで手間取りすぎた…。