LOJ2340 [WC2018] 州区划分【FMT】【欧拉回路】

题目分析：

这题是WC的题？？？

令

$g[S] = (sum_{x in S}w_x)^p$

$h[S] = g[S]$如果$S$不是欧拉回路

$d[S] = frac{f[S]}{g[All-S]^p}$

$f[S] = sum_{T subset S}d[S-T]*h[T]$

总数等于$f[All]$

代码：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int maxn = 22;
  5 const int mod = 998244353;
  6 
  7 int n,m,p,f[maxn][(1<<21)+5],g[(1<<21)+5],d[maxn][(1<<21)+5],ng[maxn][maxn];
  8 int iv[(1<<21)+5],popcnt[(1<<21)+5],w[maxn];
  9 
 10 int fast_pow(int now,int pw){
 11     int ans = 1,dt = now,bit = 1;
 12     while(bit <= pw){
 13     if(bit & pw){ans = 1ll*ans*dt%mod;}
 14     dt = 1ll*dt*dt%mod; bit<<=1;
 15     }
 16     return ans;
 17 }
 18 
 19 void read(){
 20     scanf("%d%d%d",&n,&m,&p);
 21     for(int i=1;i<(1<<n);i++) popcnt[i] = popcnt[i>>1]+(i&1);
 22     for(int i=1;i<=m;i++){
 23     int u,v; scanf("%d%d",&u,&v);
 24     ng[u][v] = ng[v][u] = 1;
 25     }
 26     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
 27 }
 28 
 29 void dp(int now){
 30     if(g[now] || now == 0) return;
 31     dp(now-(now&-now));
 32     g[now] = g[now-(now&-now)];
 33     for(int i=1;i<=n;i++) if((1<<i-1)&(now&-now)) g[now] += w[i];
 34 }
 35 
 36 queue<int> q;int arr[maxn];
 37 int chk(int now){
 38     for(int i=0;i<n;i++) if(now&(1<<i)){arr[i+1]=now;q.push(i+1);break;}
 39     while(!q.empty()){
 40     int k = q.front();q.pop();
 41     for(int i=1;i<=n;i++){
 42         if(!(now&(1<<i-1)) || !ng[k][i] || arr[i]==now) continue;
 43         arr[i] = now; q.push(i);
 44     }
 45     }
 46     for(int i=1;i<=n;i++) if(now&(1<<i-1)) if(arr[i]!=now) return 0;
 47     for(int i=1;i<=n;i++){
 48     if(!(now&(1<<i-1))) continue;
 49     int cnt = 0;
 50     for(int j=1;j<=n;j++){if((now&(1<<j-1))&&ng[i][j]) cnt++;}
 51     if(cnt & 1) return 0;
 52     }
 53     return 1;
 54 }
 55 
 56 void FMT(int *A){
 57     for(int i=1;i<(1<<n);i<<=1)
 58     for(int j=0;j<(1<<n);j+=(i<<1))
 59         for(int k=0;k<i;k++) {
 60         A[j+k+i] += A[j+k];
 61         if(A[j+k+i] >= mod) A[j+k+i] -= mod;
 62         }
 63 }
 64 
 65 void IFMT(int *A){
 66     for(int i=(1<<n-1);i>=1;i>>=1)
 67     for(int j=0;j<(1<<n);j+=(i<<1))
 68         for(int k=0;k<i;k++){
 69         A[j+k+i] -= A[j+k];
 70         if(A[j+k+i] < 0) A[j+k+i] += mod;
 71         }
 72 }
 73 
 74 void init(){
 75     for(int i=1;i<(1<<n);i++) dp(i);
 76     for(int i=1;i<(1<<n);i++){if(p==0)g[i]=1;else if(p==2)g[i]=g[i]*g[i];}
 77     for(int i=1;i<(1<<n);i++) iv[i] = fast_pow(g[i],mod-2);
 78     for(int i=1;i<(1<<n);i++){
 79     if(chk(i)) continue; // if it's Euler Graph
 80     int z = 0,p = i; while(p) {if(p&1)z++;p>>=1;}
 81     d[z][i] = g[i];
 82     }
 83     for(int i=1;i<=n;i++)
 84     FMT(d[i]);
 85     for(int i=0;i<(1<<n);i++) f[0][i] = iv[(1<<n)-1];
 86 }
 87 
 88 void work(){
 89     for(int i=2;i<=n;i++){
 90     for(int j=0;j<i;j++){
 91         for(int k=0;k<(1<<n);k++){
 92         f[i][k] += 1ll*f[j][k]*d[i-j][k]%mod;
 93         if(f[i][k] >= mod) f[i][k] -= mod;
 94         }
 95     }
 96     IFMT(f[i]);
 97     if(i < n){
 98         for(int j=0;j<(1<<n);j++){
 99         if(popcnt[j] != i) f[i][j] = 0;
100         else{f[i][j] = 1ll*f[i][j]*iv[(1<<n)-j-1]%mod;}
101         }
102         FMT(f[i]);
103     }
104     }
105     printf("%d
",f[n][(1<<n)-1]);
106 }
107 
108 int main(){
109     read();
110     init();
111     work();
112     return 0;
113 }

LOJ2340 [WC2018] 州区划分 【FMT】【欧拉回路】

LOJ2340 [WC2018] 州区划分【FMT】【欧拉回路】