猜了一个正确结论,写了个错的模拟图合并,以为结论是假的,然后扔了(

赛后兔D了我一下,我才发现(

赛后想了一下觉得得到结论后不难(

contest link
link


考虑$G_i$确定的情况下$H$的联通块个数。

首先这个乘法显然具有交换律和结合律。

如果$G_i$不联通,H联通块个数一定为$G_i$每个联通块和其它$G_j$乘起来的连通块个数和。

那么考虑$G_i$都是联通块的情况。

如果存在一个$G_i$点数为1,那么乘起来没有边,连通块个数是$\prod G_i$。

否则联通块个数是$2^{s}$,$s=max(0,$ $G_i$中二分图的连通块个数$-1)$。(我猜到了这个结论 以为它假了)

大概的证明:

以两个联通图$G_1,G_2$为例:

如果$G_1,G_2$都是二分图,那么$G_1\ast G_2$中每个点一定有黑+黑,黑+白,白+黑,白+白四种情况,用11,10,01,00表示,容易发现11只能和00连边,10只能和01连边,于是就会得到两个二分图。

任意两个在同一张图中的点$(u_1,u_2),(v_1,v_2)$都满足$G_1$中$u_1,v_1$联通,$G_2$中$u_2,v_2$联通,且随意各找一条路径奇偶性都相同。由于不要求简单路径,所以存在长度为x的路径就存在x+2的路径,所以一定存在一条$u_1$到$v_1$的路径,$u_2$到$v_2$的路径使得长度相等,所以$(u_1,u_2)$和$(v_1,v_2)$联通。

如果$G_1,G_2$有一个是二分图,不妨设$G_1$是二分图。那么$(u_1,u_2)$和$(v_1,v_2)$可能有边仅当$u_1,v_1$在$G_1$中奇偶性不同,所以还是个二分图,由于$G_2$有奇环,所以$u_2$到$v_2$的路径有奇数长度也有偶数长度,类似得$(u_1,u_2)$和$(v_1,v_2)$联通。

如果$G_1,G_2$都不是二分图,类似可得$G_1\ast G_2$是联通图,不是二分图。

类似可得多个图也满足条件。

考虑计算答案:

枚举每个图中一个联通块计算贡献。

如果联通块大小为$i$方案数$\times$贡献为$f_i$,则$n$个点的贡献为$g_n=\sum_{0\leq i\leq n}f_i\binom{n}{i}$。

则总贡献为$\prod g_{a_i}$

首先联通图的生成函数为$F=\ln G$,其中$G(x)=\sum_{i\geq 0} x^i 2^{\binom{i}{2}}$为无向图的生成函数。

对于存在一个只有1个点的联通块的情况,考虑容斥 块大小任意的贡献和-块大小不为1的贡献和。不限制块大小的情况下,大小为$x$的联通块的贡献为$x$,方案数$\times$ 贡献为$F_x\cdot x$。

对于不存在只有1个点的联通块的情况,如果所有连通块中二分图个数$\gt 0$,那么贡献为$\frac{2^{s-1}}=\frac{2^s}{2}$,其中$s$是二分图个数,如果个数$=0$,那么贡献为$1=\frac{2^0}{2}+\frac{2^0}{2}$。

于是先不考虑二分图个数是否为0,每个联通块如果是二分图贡献为2,否则为1,最后$/2$。

再加上二分图个数为0的情况的贡献,每个联通块如果不是二分图贡献为1,否则为0,最后$/2$。

考虑计算联通二分图的生成函数$H(x)$。

设$A(x)=\sum A_ix^i$,$A_n=\sum_{0\leq i\leq n}2^{i(n-i)}\binom{n}{i}=2^{\binom{n}{2}}\sum_{0\leq i\leq n}2^{-\binom{i}{2}}2^{-\binom{n-i}{2}}\binom{n}{i}$。

也就是说每个点黑白染色,不允许黑点间,白点间连边,黑点白点间任意连边的方案数。

对于每个联通块分成黑白两部分,黑白可以交换。

所以$A=e^{2H},H=\frac{\ln A}{2}$。

联通非二分图生成函数显然是$F-H$。

于是做完了。

//省略了长长的多项式板子
int f[266667],g[266667],h[266667],fac[266667],inv[266667],invf[266667];
int C(int a,int b){return fac[a]*invf[b]%p*invf[a-b]%p;}
int gr[266667],igr[266667];
int a[100005],w1[266667],w2[266667],w3[266667];
//w1 连通图个数
//w3 联通二分图个数
int s1[266667],s2[266667],s3[266667],s4[266667];
signed main(){
#ifdef QAQAutoMaton 
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
#endif
    int n=0,m;
    read(m);
    for(int i=1;i<=m;++i){
        read(a[i]);
        chkmax(n,a[i]);
    }
    fac[0]=fac[1]=::inv[1]=invf[0]=invf[1]=1;
    for(int i=2;i<=n;++i){
        fac[i]=fac[i-1]*i%p;
        ::inv[i]=(p-p/i)*::inv[p%i]%p;
        invf[i]=::inv[i]*invf[i-1]%p;
    }
    for(int i=0;i<=n;++i){
        gr[i]=fpm(2,i*(i-1)>>1);
        igr[i]=fpm((p+1)>>1,i*(i-1)>>1);
        f[i]=gr[i]*invf[i]%p;
    }
    ln(n+1,f,w1);
    for(int i=0;i<=n;++i){
        w1[i]=w1[i]*fac[i]%p;
        f[i]=igr[i]*invf[i]%p;
    }
    Mul(n,f,n,f,g);
    for(int i=0;i<=n;++i)w2[i]=g[i]*gr[i]%p;
    ln(n+1,w2,w3);
    w3[1]=0;
    for(int i=2;i<=n;++i){
        w3[i]=w3[i]*fac[i]%p*::inv[2]%p;
    }
    f[0]=f[1]=0;
    for(int i=0;i<=n;++i)
        g[i]=gr[i]*invf[i]%p;
    for(int i=2;i<=n;++i){
        f[i]=(w1[i]+w3[i])*invf[i]%p;
    }
    Mul(n,f,n,g,h);
    for(int i=0;i<=n;++i)s1[i]=h[i]*fac[i]%p;
    for(int i=2;i<=n;++i){
        f[i]=(w1[i]+p-w3[i])*invf[i]%p;
    }
    Mul(n,f,n,g,h);
    for(int i=0;i<=n;++i)s2[i]=h[i]*fac[i]%p;

    for(int i=1;i<=n;++i){
        f[i]=w1[i]*i%p*invf[i]%p;
    }
    Mul(n,f,n,g,h);
    for(int i=0;i<=n;++i)s3[i]=h[i]*fac[i]%p;
    f[1]=0;
    Mul(n,f,n,g,h);
    for(int i=0;i<=n;++i)s4[i]=h[i]*fac[i]%p;


    int w1=1,w2=1,w3=1,w4=1;
    for(int i=1;i<=m;++i){
        w1=w1*s1[a[i]]%p;
        w2=w2*s2[a[i]]%p;
        w3=w3*s3[a[i]]%p;
        w4=w4*s4[a[i]]%p;
    }
    write(((w1+w2)*::inv[2]+(w3+p-w4))%p,'\n');
    return 0;
}

标签: 计数

添加新评论