P4221

· · 个人记录

P4221 [WC2018]州区划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

有大佬说这题简单，蒟蒻表示非常的不理解。

题意：无向图 <V,E>，进行分割，使每个块没有欧拉路。求：

\sum \prod\left(\frac{\sum_{i\in v_k} w_i}{\sum_{i\in v_g,g\le k}\sum w_i}\right)

考虑拆分式子。

f(i)=\prod \left(\frac{\sum_{i\in v_k} w_i}{\sum_{i\in v_g,g\le k}\sum w_i}\right) f(i)=f(i-1)\left(\frac{\sum_{i\in v_k} w_i}{\sum_{i\in v_g,g\le k}\sum w_i}\right)[<v_k>\text{has no euler road}] f(0)=1

这样我们把它拆成“递推式”，可以通过枚举 bitmask 来进行转移。

写出转移式：

f(S)=\sum_{s\subset S}f(S \oplus s)\frac{g(s)}{g(S)}[s\ \text{has no euler road}] f(S)=\frac{1}{g(S)}\sum_{s\subset S}f(S \oplus s)g(s)[s\ \text{has no euler road}]

其中

g(S)=\sum_{i\in S}w_i

这样暴力是 O(3^n) ，期望得分 15 pts。

考虑子集卷积，需要解决的问题是 f 既出现在等式左边又在右边，所以没法直接卷积。

考虑升维。

f(S,|S|)=\frac{1}{g(S)}\sum_{s\subset S}f(S \oplus s,|S \oplus s|)g(s)[s\ \text{has no euler road}]

很好的一个性质：考虑放弃枚举 s=\varnothing（此时 g(s)=0），得到

|S\oplus s|<|S|

于是直接 \phi 卷积就行。

本题非常卡常，需要拆掉矩阵手动优化，不能用 STL 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int N=(1<<21)+1,M=5e6+10,mod=998244353;
int sf(int x){
    return (x%mod+mod)%mod;
}
int a[22][N],b[22][N];

void phior(int lim,int a[]){// phi transform
    for(int mid=1;mid<lim;mid<<=1){
        for(int w=mid<<1,i=0;i<lim;i+=w){
            rep(j,0,mid-1){
                a[i+j+mid]+=a[i+j];
            }
        }
    }
    rep(i,0,lim-1)a[i]=(a[i]%mod+mod)%mod;
}
void phinor(int lim,int a[]){// Iphi transform
    for(int mid=1;mid<lim;mid<<=1){
        for(int w=mid<<1,i=0;i<lim;i+=w){
            rep(j,0,mid-1){
                a[i+j+mid]-=a[i+j];
            }
        }
    }
    rep(i,0,lim-1)a[i]=(a[i]%mod+mod)%mod;
}
int n,m,p;
int w[22];
int wh[N],sh[N];
struct pr{
    int F,S;
};
pr g[502];
int ny[M];
int qpow(int x,int y){
    if(y==0){
        return (x==0)?0:1;
    }
    if(y==1)return x;
    if(y==2)return x*x%mod;
}
int fa[22],col[22],rd[22];
int find(int x){
    if(fa[x]==x)return x;
    else return fa[x]=find(fa[x]);
}
int f[N];
int submul(int lg){
    int lim=1<<lg;
    rep(i,0,lim-1){
        a[__builtin_popcount(i)][i]=wh[i];
        b[__builtin_popcount(i)][i]=f[i];
    }
    phior(lim,b[0]);
    rep(i,1,lg){
        phior(lim,a[i]);
    }
    rep(i,1,lg){
        rep(j,0,lim-1){
            rep(s,1,i){
                b[i][j]=(b[i][j]+a[s][j]*b[i-s][j])%mod;
            }
        }
        phinor(lim,b[i]);
        rep(j,0,lim-1){
            b[i][j]=b[i][j]*ny[sh[j]]%mod;
        }
        phior(lim,b[i]);
    }
    phinor(lim,b[lg]);
    return b[lg][lim-1];
}
int lowbit(int x){
    return x&(-x);
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&p);
    int u,v;
    rep(i,1,m){
        scanf("%lld%lld",&u,&v);
        g[i]={u-1,v-1};
    }
    rep(i,0,n-1){
        scanf("%lld",w+i);
    }
    int lim=(1<<n);
    rep(i,0,lim-1){
        rep(j,0,n-1){
            if((1<<j)&i){
                col[j]=i;
                fa[j]=j;rd[j]=0;
                sh[i]+=w[j];
            }
        }
        rep(k,1,m){
            if(col[g[k].F]==i&&col[g[k].S]==i){
                rd[g[k].F]++;
                rd[g[k].S]++;
                fa[find(g[k].F)]=find(g[k].S);
            }
        }
        int lst=-1;
        bool good=0;
        rep(j,0,n-1){
            if((1<<j)&i){
                if(lst!=-1){
                    if(find(lst)!=find(j)){
                        good=1;
                    }
                }
                lst=j;
            }
        }
        if(!good){
            rep(j,0,n-1){
                if((1<<j)&i){
                    if(rd[j]%2==1){
                        good=1;
                    }
                }
            }
        }
        if(good){
            rep(j,0,n-1){
                if((1<<j)&i){
                    wh[i]+=w[j];
                }
            }
        }
    }
    ny[1]=1;
    rep(i,2,M-1){
        ny[i]=sf(-ny[mod%i]*(mod/i));
    }
    rep(i,0,lim-1){
        wh[i]=qpow(wh[i],p);
        sh[i]=qpow(sh[i],p);
    }
    f[0]=1;
    printf("%lld\n",submul(n));
}