题解归档 - cf2233E1

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

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

思路

cf2233E1/E2 - Permutation Transmission

pattern:
unlabeled coordinates / Boolean downset

columns:
After reading the received rows, each original position gives one m-bit
column mask, where m=ceil(log2(n+1)). For a valid permutation these masks,
after some coordinate permutation, must be exactly the binary masks 1..n.

validity:
Add mask 0. The standard set {0,1,...,n} is a downset: every submask of a
present mask is also present. Coordinate permutations preserve this property.
The standard bit rows have fixed one-counts; coordinate permutations only
permute those counts.

The used criterion is:

• all received column masks are distinct and nonzero;
• after adding 0, the set of masks is closed under deleting one set bit;
• the multiset of received row one-counts equals the multiset of one-counts of
  standard bit positions over numbers 1..n.

For this threshold downset, these conditions determine the set up to coordinate
permutation.

answer:
If invalid, answer is 0. Otherwise, every group of standard bit positions
with the same one-count can be permuted freely, and no other bit positions can.
Therefore answer is the product of factorials of equal-count group sizes.

check:
For small n, brute.cpp enumerates all bit-coordinate permutations and
counts distinct resulting permutations.

代码

来源：problems/cf2233E1/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;
}