LOJ#2340. 「WC2018」州区划分

感觉是比较基础的子集 DP.

令 $dp[S]$ 表示点集 $S$ 构成的价值和，然后枚举最后一个区域就行.

也就是 $dp[S]=sum_{T subseteq S } dp[S-T] imes (frac{sum[T]}{sum[S]})^k$

化简得 $dp[S] imes sum[S]^k = sum_{T subseteq S} dp[S-T] imes sum[T]^k$      

如何判断欧拉回路：

所有点的度数都是偶数，就有欧拉回路.

然后在做子集卷积的时候要注意：很多项是无用的，要手动清空.

code: 

#include <bits/stdc++.h>      
#define N 22   
#define ll long long 
#define mod 998244353    
#define lb(x) ((x)&(-(x)))
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;          
int n,m,P,lim;    
int a[N][N],w[N],b[N],vis[N],cnt[1<<N],g[N][1<<N];  
int deg[1<<N],sum[1<<N],Log[1<<N],check[1<<N],dp[N][1<<N],f[1<<N],invf[1<<N];         
void dfs(int x,int sta) 
{   
    vis[x]=sta;   
    for(int i=1;i<=n;++i)  
        if(a[x][i]&&vis[i]!=sta&&(b[i-1]&sta)) dfs(i,sta);   
}      
int qpow(int x,int y) 
{
    int tmp=1; 
    for(;y;y>>=1,x=(ll)x*x%mod) if(y&1) tmp=(ll)tmp*x%mod;  
    return tmp; 
}  
int INV(int x) { return qpow(x,mod-2); }       
void FWT(int *A) 
{
    for(int len=1;len<lim;len<<=1) 
        for(int i=0;i<lim;i+=len<<1)  
            for(int j=0;j<len;++j)       
                A[i+j+len]+=A[i+j],A[i+j+len]>=mod?A[i+j+len]-=mod:0;  
}   
void IFWT(int *A) 
{
    for(int len=1;len<lim;len<<=1) 
        for(int i=0;i<lim;i+=len<<1)  
            for(int j=0;j<len;++j)   
                A[i+j+len]-=A[i+j],A[i+j+len]<0?A[i+j+len]+=mod:0;   
}
int main() 
{ 
    // setIO("input");       
    int x,y,z; 
    scanf("%d%d%d",&n,&m,&P),lim=1<<n;            
    for(int i=0;i<=n;++i)  Log[1<<i]=i,b[i]=1<<i;  
    for(int i=1;i<=m;++i)  scanf("%d%d",&x,&y),a[x][y]=a[y][x]=1;  
    for(int i=1;i<=n;++i) scanf("%d",&w[i]);    
    for(int i=1;i<(1<<n);++i) 
    { 
        x=i-lb(i),y=Log[lb(i)]+1;        
        sum[i]=sum[x]+w[y],deg[i]=deg[x],cnt[i]=cnt[x]+1;         
        for(int j=1;j<=n;++j)        
            if(a[y][j]&&(b[j-1]&x)) deg[i]^=b[j-1]^b[y-1];                           
        if(deg[i]) check[i]=1;  
        else 
        {
            dfs(y,i);         
            check[i]=0;  
            for(int j=1;j<=n;++j) 
                if((b[j-1]&i)&&vis[j]!=i) check[i]=1;   
        }    
        f[i]=qpow(sum[i],P),invf[i]=INV(f[i]);         
    }          
    for(int i=1;i<lim;++i) g[cnt[i]][i]=f[i]*check[i];                   
    dp[0][0]=1,FWT(dp[0]);    
    for(int i=1;i<=n;++i)  FWT(g[i]);  
    for(int i=1;i<=n;++i) 
    {
        for(int j=0;j<i;++j)                
            for(int k=0;k<lim;++k)  
                dp[i][k]+=(ll)dp[j][k]*g[i-j][k]%mod,dp[i][k]>=mod?dp[i][k]-=mod:0;     
        IFWT(dp[i]);      
        for(int j=0;j<lim;++j)     
            dp[i][j]=(cnt[j]==i)?(ll)dp[i][j]*invf[j]%mod:0;
        FWT(dp[i]);   
    }   
    printf("%d
",dp[n][(1<<n)-1]);  
    return 0; 
}