Codeforces ECR #191 : E2. Permutation Transmission (Difficult Version)

いまいち確証がないまま解いてしまった。
https://codeforces.com/contest/2233/problem/E2

問題

1～NのPermutation Pがある。
ここにlogN個の、N文字のバイナリ文字列S[i]が与えられる。

S[i]は、Pの各要素のどこかのbitの値だけを並べたものである。
このSを生成できるPは何通りか。

解法

1～Nについて、各bitで1が何個あるかを数えよう。
２進数表記で上の桁ほど1の数が減るので、Sの並び順を１個定め、Pを復元できるか確認する。
復元できた場合は、1の個数が一致するS[i]同士は互いに入れ替えてもよい。

int S[20][201010];

int T,N,L;
string V[20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,20) {
		FOR(j,200010) {
			S[i][j+1]=S[i][j]+((j+1)>>i)%2;
			if(i&&S[i-1][j]<S[i][j]) {
			}
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>N;
		x=N;
		L=0;
		while(x) x/=2,L++;
		vector<pair<int,string>> P;
		N++;
		FOR(i,L) {
			cin>>V[i];
			V[i]+='0';
			P.push_back({count(ALL(V[i]),'1'),V[i]});
		}
		sort(ALL(P));
		set<int> Q;
		map<int,int> C;
		ll ret=1;
		FOR(i,L) {
			if(P[i].first!=S[L-1-i][N-1]) {
				ret=0;
				break;
			}
			ret*=++C[P[i].first];
		}
		FOR(x,N) {
			y=0;
			FOR(i,L) if(P[i].second[x]=='1') y|=1<<(L-1-i);
			Q.insert(y);
		}
		
		if(Q.size()!=N||*Q.rbegin()!=N-1) ret=0;
		cout<<ret<<endl;
	}
}

まとめ

えいやで解いてしまって反省。