題目傳送門：http://uoj.ac/problem/94

　　這是一道集合冪級數的入門題目。我們先考慮求出每個點集的連通生成子圖個數，記為$g_S$，再記$h_S$為點集$S$的生成子圖個數，容易發現，$h_S=2^{size_S}$，其中$size_S$為點集$S$的極大生成子圖內的邊數。特殊的，$f_{\o}=g_{\o}=0$。

　　定義集合冪級數的乘法為子集卷積，考慮集合冪級數$h$和$g$的關系，我們可以得到

　　　　$$h=1+\sum_{k \geq 1}\frac{g^k}{k!}=1+e^h$$

?

　　因此可得

　　　　$$g=\ln{(1+h)}$$

　　我們再記$f_S$為點集$S$的生成子圖的價值和，可得到

　　　　$$f=1+\sum{k \geq 1}\frac{g^k}{k!}k!=\frac{1}{1-g}$$

　　計算集合冪級數的對數和逆時，因為我們將乘法定義為子集卷積，所以可以將其映射成集合占位冪級數$f_{|S|,S}$后，在將每個集合對應的位看作形式冪級數再暴力求解。

　　代碼：

#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #define mod 998244353 #define Mod1(x) (x>=mod?x-mod:x) #define Mod2(x) (x<0?x+mod:x) #define ll long long inline ll read() {ll x=0; char c=getchar(),f=1;for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';return x*f; } inline void write(ll x) {static int buf[20],len; len=0;if(x<0)x=-x,putchar('-');for(;x;x/=10)buf[len++]=x%10;if(!len)putchar('0');else while(len)putchar(buf[--len]+'0'); } inline void writeln(ll x){write(x); putchar('\n');} inline void writesp(ll x){write(x); putchar(' ');} int f[25][(1<<20)+5],g[25][(1<<20)+5]; int cnt[(1<<20)+5],inv[25]; int x[410],y[410]; int n,m; inline ll power(ll a,ll b) {ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans; } inline void fwt(int* a,int n) {for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=(i<<1))for(int k=j;k<j+i;k++)a[k+i]=Mod1(a[k+i]+a[k]); } inline void ifwt(int* a,int n) {for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=(i<<1))for(int k=j;k<j+i;k++)a[k+i]=Mod2(a[k+i]-a[k]); } int main() {n=read(); m=read();for(int i=0;i<m;i++)x[i]=read()-1,y[i]=read()-1;for(int i=1;i<1<<n;i++)cnt[i]=cnt[i>>1]+(i&1);for(int i=1;i<1<<n;i++){int tot=0;for(int j=0;j<m;j++)if((i&(1<<x[j]))&&(i&(1<<y[j])))++tot;f[cnt[i]][i]=power(2,tot);}for(int i=1;i<=n;i++)fwt(f[i],1<<n);for(int i=1;i<=n;i++)inv[i]=power(i,mod-2);for(int i=1;i<=n;i++){\\求lnfor(int k=0;k<i;k++)for(int j=0;j<1<<n;j++)g[i][j]=(g[i][j]+(ll)k*g[k][j]%mod*f[i-k][j])%mod;for(int j=0;j<1<<n;j++)g[i][j]=(f[i][j]+(ll)(mod-inv[i])*g[i][j])%mod;}memset(f,0,sizeof(f));for(int i=0;i<1<<n;i++)f[0][i]=1;for(int i=1;i<=n;i++)\\求逆for(int k=0;k<i;k++)for(int j=0;j<1<<n;j++)f[i][j]=(f[i][j]+(ll)f[k][j]*g[i-k][j])%mod;ifwt(f[n],1<<n);writeln(f[n][(1<<n)-1]);return 0; } uoj94

?

轉載于:https://www.cnblogs.com/quzhizhou/p/11311381.html

總結

以上是生活随笔為你收集整理的【uoj#94】【集训队互测2015】胡策的统计（集合幂级数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。