[2016北京集训试题8]连在一起的幻想乡[dp+无向图计数]

Description

Solution

本博客参考yww大佬的博客，为了加深理解我就自己再写一遍啦。

以下的“无向图”均无重边无自环。

定义f0[n]为n个点构成的无向图个数,f1[n]为n个点构成的无向图的总边数，f2[n]为所有(n个点构成的无向图的边数的平方)之和。

g0[n]为n个点构成的连通无向图个数,g1[n]为n个点构成的连通无向图的总边数，g2[n]为所有(n个点构成的连通无向图的边数的平方)之和。

设$m[i]=i*(i-1)/2$

每条边可以选或不选，所以$f0[i]=2^{m[i]}$

由于每条边会在$2^{m[i]-1}$个图中被选，$f1[i]=m[i]*2^{m[i]-1}$

求f2的公式要运用一个套路：枚举与1号点连通的边数j，则$f2[i]=\sum_{j=0}^{i-1}*\sum _{k=0}^{m[i]-j}*((j+k)^{2}$*(i-1个点的无向图边数为k的个数))

即$f2[i]=\sum_{j=0}^{n-1}$*[(i-1个点无向图个数*j）的平方+2*j*(i-1个点无向图总边数)+所有(i-1个点构成的无向图的边数的平方)之和）

故$f2[i]=\sum_{j=0}^{n-1}*\binom{i-1}{j}*(f2[i-1]+2*j*f1[i-1]+j^{2}*f0[i-1])$。

我们枚举点1所在连通块点数，$g0[i]=f0[i]-\sum _{j=1}^{i-1}*\binom{i-1}{j-1}g0[j]*f0[i-j]$
$g1[i]=f1[i]-\sum _{j=1}^{i-1}*\binom{i-1}{j-1}(g0[j]*f1[i-j]+g1[j]*f0[i-j])$

$g2[i]=f2[i]-\sum _{j=1}^{i-1}*\binom{i-1}{j-1}(g0[j]*f2[i-j]+2*g1[j]*f1[i-j]+g2[j]*f0[i-j])$

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

int n,mod;

ll C[][],m[],g0[],g1[],g2[],f0[],f1[],f2[];

ll ksm(ll x,ll k)

{ll re=;if (k==-) return ;while (k){if (k&)re=re*x%mod;k>>=;x=x*x%mod;}return re;}

int main()

{

    scanf("%d%d",&n,&mod);

    for (int i=;i<=n;i++) C[i][]=;

    for (int i=;i<=n;i++) for (int j=;j<=i;j++) C[i][j]=(C[i-][j]+C[i-][j-])%mod;

    for (int i=;i<=n;i++) m[i]=i*(i-)/;

    for (int i=;i<=n;i++) f0[i]=ksm(,m[i]),f1[i]=m[i]*ksm(,m[i]-)%mod;

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

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

        f2[i]=(f2[i]+(f2[i-]+*j*f1[i-]+j*j*f0[i-])%mod*C[i-][j]%mod+mod)%mod;

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

    {

        g0[i]=f0[i];g1[i]=f1[i];g2[i]=f2[i];

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

        {

            g0[i]=(g0[i]-C[i-][j-]*g0[j]%mod*f0[i-j]%mod+mod)%mod;

            g1[i]=(g1[i]-C[i-][j-]*((g0[j]*f1[i-j]+g1[j]*f0[i-j])%mod)%mod+mod)%mod;

            g2[i]=(g2[i]-C[i-][j-]*((g0[j]*f2[i-j]+*g1[j]*f1[i-j]+g2[j]*f0[i-j])%mod)%mod+mod)%mod;

        }

    }

    printf("%lld",g2[n]);

}