[NOIP模拟测试3] 建造游乐园题解（欧拉图性质）

Orz 出题人石二队爷

我们可以先求出有n个点的联通欧拉图数量，然后使它删或增一条边得到我们要求的方案

也就是让它乘上$C_n^2$ (n个点里选2个点，要么删边要么连边，选择唯一)

那么接下来就是求有n个点的联通欧拉图数量$f[n]$

首先来看欧拉图的定义：

一张无向图为欧拉图，当且仅当无向图连通，并且每个点的度数都是偶数。

那么设共有n个点且所有点度数皆为偶数的方案数为$g[n]$

之后尝试计算出来它

先把一个点拿出来，剩$n-1$个点

从这$n-1$个点中选2个点，这两点之间可以连或不连边

那么如果最终某个点的度数不为偶，就用之前单拿出来的点向他连边

最后有一个问题：如果单拿出来的点度数不为偶呢？

显然不可能。每条边对总度数的贡献为2，所以无重边无自环的话一定满足要求

可得

$g_i=2^{C_{i-1}^2}$

接下来应当让$g$中的方案保证联通即为$f$

正如上场T3一样，考虑总-目标之外

枚举$j=1->i-1$ 得到$f_j$是一部分点满足欧拉图性质的方案数

则$g_{i-j}$是剩下点满足度数为偶的方案数

我们现在要构造除了所求之外的情况，所以从那i个点里拿出一个，从剩下的里面选$j-1$个点连边

$f_i=g_i-\sum \limits_{j=1}^{i-1}{f_j*g_{i-j}*C_{i-1}^{j-1}}$

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int mod=1e9+;

typedef long long ll;

int n;

ll qpow(ll a,ll b)

{

    ll res=;

    a%=mod;

    while(b)

    {

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

        a=(a*a)%mod;

        b>>=;

    }

    return res%mod;

}

ll C[][],g[],f[];

int main()

{

    scanf("%d",&n);

    C[][]=;

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

    {

        C[i][]=;

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

            C[i][j]=C[i-][j]+C[i-][j-],C[i][j]%=mod;

    }

//    while(1);

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

        g[i]=qpow(,C[i-][]);

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

    {

        f[i]=g[i];

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

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

    }

    cout<<f[n]*C[n][]%mod<<endl;

    return ;

}

巴特西

[NOIP模拟测试3] 建造游乐园题解（欧拉图性质）

最新文章

热门文章

巴特西

[NOIP模拟测试3] 建造游乐园 题解（欧拉图性质）

最新文章

热门文章

[NOIP模拟测试3] 建造游乐园题解（欧拉图性质）