题解 P7341【『MdOI R4』Phoenix】

· · 题解

前言：

感谢zyk对我的指导，我才得以写出这题。

2k 代码调了将近 3h 才调出来，看起来我的代码能力还需提高。

题解：

不难发现，一个满足条件的把集合排列好的排列，必须满足对于 [1,m] 的每一种数，都存在一个区间，满足区间中的集合都包含这种数，并且区间外的集合都不包含这种数。

设 Solve(v,t) 考虑 v 中这些集合，t 中这些种类的数的方案数。v 满足在最终排列中一定是连续的一段（即一定紧挨在一起）。

考虑找到一个 t 的子集 z，使得 v 中的数可以根据和 z 的交集再划分成若干个必须挨在一起的集合的集合，然后答案乘上这些集合的集合的合法排列方案。

对于 t 中数 x，设 c_x 表示 v 中包含 x 的集合构成的集合。

考虑先找到那些不存在另一个数 y 使得 c_x\subset c_y 的集合 x。

如果直接按这些 x 构成的 z 划分集合，会 WA 一片。

拍一拍会发现问题出在有的数非常讨厌，比如一个数 x，虽然它会被某个 c_y 包含，但是 c_x 中存在两个集合使得这两个集合和 z 的交集不同，如果 x 不在 z 中就 GG 了，所以需要把 x 加进 z 中。

具体如何统计答案建议自行思考。实现细节可以参考代码。

时间复杂度：\mathcal{O}(nm^2)。但是常数特别小，最慢点50ms。

code:


/*
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
*/

const int mod=998244353;

int T,n,m,fac[N];
ull a[N];
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=1LL*fac[i-1]*i%mod;
    }
}
struct Union_Set{
    int f[64],s[64];
    void init(int n){
        for(int i=0;i<n;++i)f[i]=i,s[i]=1;
    }
    int getf(int x){
        return f[x]==x?x:f[x]=getf(f[x]);
    }
    int Merge(int x,int y){
        int fx=getf(x),fy=getf(y);
        if(fx==fy)return 0;
        s[fx]+=s[fy],s[fy]=0;
        f[fy]=fx;
        return 1;
    }
};
int Solve(vector<ull> &p,ull t){
    ull z=0;
    static int cnt[64];
    memset(cnt,0,sizeof(cnt));
    bool same=true;
    for(int i=1;i<(int)p.size();++i){
        if(p[i]^p[0]){same=false;break;}
    }
    if(same)return fac[p.size()];
    for(auto x:p){
        for(int i=0;i<m;++i){
            if(x>>i&1)++cnt[i];
        }
    }
    for(int i=0;i<m;++i){
        if(t>>i&1){
            ull all=(1uLL<<m)-1;
            for(auto x:p){
                if(x>>i&1)all&=x;
            }
            bool ok=true;
            for(int j=0;j<m&&ok;++j){
                if(i==j||cnt[j]<cnt[i]||(cnt[j]==cnt[i]&&i<j))continue;
                if(all>>j&1){
                    ok=false;break;
                }
            }
            if(ok)z|=1uLL<<i;
        }
    }
    while(true){
        bool qwq=false;
        for(int i=0;i<m;++i){
            if(t>>i&1&&!(z>>i&1)){
                ull tmp=~0uLL;
                for(auto x:p){
                    if(x>>i&1){
                        ull g=(x&z);
                        if(~tmp&&tmp^g){
                            z|=1uLL<<i;qwq=true;
                            break;
                        } 
                        tmp=g;
                    }
                }
            }
        }
        if(!qwq)break;
    }
    int res=1;
    map<ull,vector<ull> > mp;
    int rem=__builtin_popcountll(z);
    for(auto x:p){
        if(x){
            mp[x&z].push_back(x^(x&z));
        }
        else ++rem;
    }
    Union_Set S;
    S.init(m);
    for(auto [d,s]:mp){
        res=1LL*res*Solve(s,t^z)%mod;
        for(int i=0;i<m;++i){
            if(d>>i&1){
                for(int j=0;j<m;++j){
                    if(d>>j&1)rem-=S.Merge(i,j);
                }
            }
        }
    }
    for(int i=0;i<m;++i){
        if(z>>i&1&&S.s[i]>1)(res<<=1)%=mod;
    }
    return 1LL*res*fac[rem]%mod;
}
int main(){
    init(100000);
    T=read();
    int cnt=0;
    while(T--){
        ++cnt;
        n=read(),m=read();
        vector<ull> all;
        for(int i=1;i<=n;++i){
            all.push_back(read());
        }
        printf("%d\n",Solve(all,(1uLL<<m)-1));
    }
    return 0;
}