[WC2018]州区划分(FWT)

时间：2023-03-10 02:15:56
[WC2018]州区划分(FWT)

题目描述

题解

这道题的思路感觉很妙。

题目中有一个很奇怪的不合法条件，貌似和后面做题没有什么关系，所以我们先得搞掉它。

也就是判断一个点集是否合法，也就是判断这个点集是否存在欧拉回路。

如果存在欧拉回路每个点的度都得是偶数而且图联通，这个条件扫描一遍在上一个并查集就可以判掉了。

然后开始统计答案。

n很小，可以考虑状压dp，我们设dp[s]为已经划分好的州区点集和为s它的所有方案的答案的和。

转移可以考虑枚举子集。

dp[s]=∑dp[s']*(sum[s^s']/sum[s])p

然后我们发现sum[s]p是和转移的枚举无关的，所以我们可以稍稍变换一下变成
dp[s]*sum[s]p=∑dp[s']*sum[s^s']p

这样的复杂度是3n的，我们要考虑优化。

我们换一种枚举方式

dp[S]*sum[s]p=∑dp[s]*sum[s']p  (s&s'==0)&&(s|s'==S)

如果没有前面那个条件，那么它就是一个形式有点奇怪的或卷积，在加上那个烦人的条件，就有点让人怀疑人生了。。

然后关键的思路来了，考虑到这道题时限较长，复杂度可以在卷积的基础上加一个n，所以我们把dp状态多开一维。

我们设dp[i][S]表示在S点集中有i个点的答案。

这样的状态设计虽然带来了大量冗余状态，却方便了我们的转移。

dp[i][S]=∑dp[j][s]*sum[i-j][s']p  (s|s'==S)

这样我们成功的用一个n的时间复杂度把这个东西变成了一个正常的或卷积，直接上FWT就可以了。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define N 22

#define R register

using namespace std;

typedef long long ll;

int n,m,p,lowb[<<],cou[<<],size,du[N],fa[N];

ll f[N][<<],g[N][<<],w[N],sum[<<],ny[<<];

bool a[N][N],b[N];

const int mod=;

inline int rd(){

    int x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

inline ll power(ll x,ll y){

    ll ans=;

    while(y){if(y&)ans=ans*x%mod;x=x*x%mod;y>>=;}

    return ans;

}

inline ll ni(ll x){return power(x,mod-);}

inline void MOD(ll &x){x=(x+mod)%mod;}

inline void FWT(ll *a,int tag){

    for(R int i=;i<size;i<<=)

        for(R int j=;j<size;j+=(i<<))

          for(R int k=;k<i;++k)MOD(a[i+j+k]+=tag*a[j+k]);

}

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

int main(){

    n=rd();m=rd();p=rd();int u,v;size=(<<n);

    for(R int i=;i<=m;++i){u=rd();v=rd();a[u][v]=a[v][u]=;}

    for(R int i=;i<=n;++i)w[i]=rd();

    for(R int i=;i<size;i<<=)lowb[i]=lowb[i>>]+;

    for(R int s=;s<size;++s){

       cou[s]=cou[s>>]+(s&);bool haha=;int num=cou[s];

       for(R int i=;i<=n;++i){if(s&(<<i-))sum[s]+=w[i],b[i]=;else b[i]=;du[i]=;fa[i]=i;}

       for(R int i=;i<=n;++i)if(b[i])for(int j=i+;j<=n;++j)if(a[i][j]&&b[j]){

         du[i]++,du[j]++;

         int xx=find(i),yy=find(j);if(xx!=yy)fa[xx]=yy,num-=;

       }

       for(R int i=;i<=n;++i)if(du[i]&){haha=;break;}

       if(num!=)haha=;

       if(!haha)continue;

       g[cou[s]][s]=power(sum[s],p);

    }

    for(R int s=;s<size;++s)ny[s]=ni(power(sum[s],p));

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

    f[][]=;FWT(f[],);

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

        for(R int j=;j<i;++j){

            for(R int k=;k<size;++k)(f[i][k]+=f[j][k]*g[i-j][k])%=mod;

        }

        FWT(f[i],-);

        for(R int j=;j<size;++j)f[i][j]=f[i][j]*ny[j]%mod;

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

    }

    printf("%lld",f[n][size-]);

    return ;

}

相关文章