【uoj#94】【集训队互测2015】胡策的统计（集合幂级数）

　　题目传送门：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=; char c=getchar(),f=;

    for(;c<''||''<c;c=getchar())if(c=='-')f=-;

    for(;''<=c&&c<='';c=getchar())x=x*+c-'';

    return x*f;

}

inline void write(ll x)

{

    static int buf[],len; len=;

    if(x<)x=-x,putchar('-');

    for(;x;x/=)buf[len++]=x%;

    if(!len)putchar('');

    else while(len)putchar(buf[--len]+'');

}

inline void writeln(ll x){write(x); putchar('\n');}

inline void writesp(ll x){write(x); putchar(' ');}

int f[][(<<)+],g[][(<<)+];

int cnt[(<<)+],inv[];

int x[],y[];

int n,m;

inline ll power(ll a,ll b)

{

    ll ans=;

    for(;b;b>>=,a=a*a%mod)

        if(b&)ans=ans*a%mod;

    return ans;

}

inline void fwt(int* a,int n)

{

    for(int i=;i<n;i<<=)

        for(int j=;j<n;j+=(i<<))

            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=;i<n;i<<=)

        for(int j=;j<n;j+=(i<<))

            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=;i<m;i++)

        x[i]=read()-,y[i]=read()-;

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

        cnt[i]=cnt[i>>]+(i&);

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

        int tot=;

        for(int j=;j<m;j++)

            if((i&(<<x[j]))&&(i&(<<y[j])))++tot;

        f[cnt[i]][i]=power(,tot);

    }

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

        fwt(f[i],<<n);

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

        inv[i]=power(i,mod-);

    for(int i=;i<=n;i++){\\求ln

        for(int k=;k<i;k++)

            for(int j=;j<<<n;j++)

                g[i][j]=(g[i][j]+(ll)k*g[k][j]%mod*f[i-k][j])%mod;

        for(int j=;j<<<n;j++)

            g[i][j]=(f[i][j]+(ll)(mod-inv[i])*g[i][j])%mod;

    }

    memset(f,,sizeof(f));

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

        f[][i]=;

    for(int i=;i<=n;i++)\\求逆

        for(int k=;k<i;k++)

            for(int j=;j<<<n;j++)

                f[i][j]=(f[i][j]+(ll)f[k][j]*g[i-k][j])%mod;

    ifwt(f[n],<<n);

    writeln(f[n][(<<n)-]);

    return ;

}

uoj94

巴特西

【uoj#94】【集训队互测2015】胡策的统计（集合幂级数）

最新文章

热门文章