「WC2018」州区划分（FWT）

我去弄了一个升级版的博客主题，比以前好看多了。感谢 @Wider

不过我有阅读模式的话不知为何 \(\text{LATEX}\) 不能用，所以我就把这个功能删掉了。

洛谷上不开 \(O_2\) 根本过不去，自带大常数被卡到 \(15\) 分。。。

首先题了读了很久，发现一个州的集合可以不连通。。。

我们可以 \(O(n^22^n)\) 检验每一个状态是否满足条件，用并查集即可。

\(f[S]\) 为状态 \(S\) 时的满意度之和，\(g[S]\) 当状态 \(S\) 为合法状态时为 \(sum_S^p\)

然后这个东西可以用 \(or\) 卷积的 \(FWT\) 优化。我觉得出题人特地把数据范围出这么大应该是卡 \(O(3^n)\) 的枚举子集。

\(Code\ Below:\)

// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

const int mod=998244353;

int n,m,p,lim,w[30],d[30],e[30],fa[30],bin[30],cnt[1<<21],sum[1<<21],inv[1<<21],f[22][1<<21],g[22][1<<21];

inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}

inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}

inline int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}

inline int fpow(int a,int b){

    int ret=1;

    for(;b;b>>=1,a=mul(a,a))

        if(b&1) ret=mul(ret,a);

    return ret;

}

inline void FWT(int *f,int n){

    for(int len=1;len<n;len<<=1)

        for(int i=0;i<n;i++)

            if(i&len) f[i]=add(f[i],f[i^len]);

}

inline void IFWT(int *f,int n){

    for(int len=1;len<n;len<<=1)

        for(int i=0;i<n;i++)

            if(i&len) f[i]=sub(f[i],f[i^len]);

}

inline int find(int x){

    return (x==fa[x])?x:fa[x]=find(fa[x]);

}

inline bool check(int S){

    if(cnt[S]<=1) return 0;

    int tot=0;

    for(int i=0;i<n;i++) fa[i]=i,d[i]=0;

    for(int i=0;i<n;i++)

        if(S&bin[i]){

            sum[S]+=w[i];

            for(int j=i+1;j<n;j++)

                if((S&bin[j])&&(e[i]&bin[j])){

                    d[i]++;d[j]++;

                    if(find(i)!=find(j)) fa[fa[i]]=fa[j],tot++;

                }

        }

    sum[S]=(p==0)?1:(p==1)?sum[S]:sum[S]*sum[S];

    if(tot<cnt[S]-1) return 1;

    for(int i=0;i<n;i++)

        if((S&bin[i])&&(d[i]&1)) return 1;

    return 0;

}

int main()

{

    scanf("%d%d%d",&n,&m,&p);

    lim=1<<n;bin[0]=1;

    for(int i=1;i<=n;i++) bin[i]=bin[i-1]<<1;

    for(int i=1;i<lim;i++) cnt[i]=cnt[i>>1]+(i&1);

    int x,y;

    for(int i=0;i<m;i++){

        scanf("%d%d",&x,&y);

        x--;y--;

        e[x]|=bin[y];e[y]|=bin[x];

    }

    for(int i=0;i<n;i++) scanf("%d",&w[i]);

    for(int i=0;i<lim;i++){

        g[cnt[i]][i]=check(i)?sum[i]:0;

        inv[i]=fpow(sum[i],mod-2);

    }

    for(int i=0;i<=n;i++) FWT(g[i],lim);

    f[0][0]=1;FWT(f[0],lim);

    for(int i=1;i<=n;i++){

        for(int j=0;j<i;j++)

            for(int k=0;k<lim;k++) f[i][k]=add(f[i][k],mul(f[j][k],g[i-j][k]));

        IFWT(f[i],lim);

        for(int k=0;k<lim;k++) f[i][k]=(cnt[k]==i)?mul(f[i][k],inv[k]):0;

        if(i<n) FWT(f[i],lim);

    }

    printf("%d\n",f[n][lim-1]);

    return 0;

}