题解归档 - cf2233E2

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2233E2
• 本地来源：problems/cf2233E2/idea.md
• 题目链接：https://codeforces.com/contest/2233/problem/E2
• 原始标题：cf2233E2 - Permutation Transmission

思路

cf2233E2 - Permutation Transmission

Same solution as cf2233E1: build column masks, validate the unlabeled Boolean
downset, and multiply factorials of equal standard bit-row one-counts.

Complexity is O(n log n + 2^m m) per test with m=ceil(log2(n+1)); since
2^m < 2(n+1), this is linear up to a logarithmic factor under the hard
version's sum n <= 2e5.

代码

来源：problems/cf2233E2/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll fact[25];
ll bitCountOnes(int n,int b){
    ll len=(ll)n+1;
    ll per=1LL<<(b+1);
    ll half=1LL<<b;
    ll full=len/per;
    ll rem=len%per;
    return full*half+max(0LL,rem-half);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fact[0]=1;
    for(int i=1;i<25;i++) fact[i]=fact[i-1]*i;
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int m=0;
        while((1<<m)<n+1) m++;
        vector<int> col(n,0),row;
        row.reserve(m);
        string s;
        for(int r=0;r<m;r++){
            cin>>s;
            int cnt=0;
            for(int i=0;i<n;i++){
                if(s[i]=='1'){
                    cnt++;
                    col[i]|=1<<r;
                }
            }
            row.push_back(cnt);
        }
        int lim=1<<m;
        vector<char> have(lim,0);
        have[0]=1;
        bool ok=true;
        for(int x:col){
            if(have[x]) ok=false;
            else have[x]=1;
        }
        for(int mask=1;mask<lim and ok;mask++){
            if(!have[mask]) continue;
            for(int b=0;b<m;b++){
                if((mask>>b&1) and !have[mask^(1<<b)]){
                    ok=false;
                    break;
                }
            }
        }
        vector<int> need;
        for(int b=0;b<m;b++) need.push_back((int)bitCountOnes(n,b));
        sort(row.begin(),row.end());
        sort(need.begin(),need.end());
        if(row!=need) ok=false;
        if(!ok){
            cout<<0<<"\n";
            continue;
        }
        ll ans=1;
        for(int i=0;i<m;){
            int j=i;
            while(j<m and need[j]==need[i]) j++;
            ans*=fact[j-i];
            i=j;
        }
        cout<<ans<<"\n";
    }
    return 0;
}