【STSRM10】数学上来先打表

【算法】DP+数学计数

【题意】给出n个点(不同点之间有区别)，求出满足下列条件的连边（双向边）方案(对1004535809取模)：

1.每条边连接两个不同的点，每两个点之间至多有一条边。

2.不存在三个点a,b,c使三个点间两两可以互相到达且两两之间最短距离相等。

3.边的长度均为1。

n<=2000

【题解】

p[i]表示i个点形成联通块的满足条件的方案数。

如果i个点形成链，则一定是直链，如果有分支则一定不满足条件，如此有n!/2种方案（排列，正反算一种）

如果i个点形成环，则一定是i-1条边形成的大环，否则一旦有分支则一定不满足条件，如此有(n-1)!种方案（排列，多算了n次）

如果i%3=0，则大环也不满足条件，所以有0种方案。

p[n]=n!/2+(n-1)! n%3!=0

p[n]=n!/2 n%3==0

（注意p[1]=1要预处理。）

f[i]表示i个点的答案，试图枚举第i个点和谁形成了联通块。

f[i]=Σ(p[j]*f[i-j]*C(i-1,j-1)),1<=j<=i

（注意阶乘的逆元提前处理，否则常数太大）

小技巧：inv(2,p)=2^(p-2)%p=(p+1)/2

这种做法是套路：无向连通图计数！

#include<cstdio>

#include<algorithm>

#include<cstring>

#define ll long long

using namespace std;

const int maxn=,MOD=;

ll inv2=(MOD+)/;

ll n,fac[maxn],f[maxn],p[maxn],fav[maxn];

void exgcd(ll a,ll b,ll &x,ll &y)

{if(!b){x=;y=;return;}else{exgcd(b,a%b,y,x);y-=x*(a/b);}}

ll inv(ll a,ll n){

    ll x,y;

    exgcd(a,n,x,y);

    return (x%MOD+MOD)%MOD;

}

ll C(ll n,ll m){return fac[n]*fav[m]%MOD*fav[n-m]%MOD;}

int main()

{

    scanf("%lld",&n);

    f[]=p[]=fac[]=fav[]=;

    for(int i=;i<=n;i++)fac[i]=fac[i-]*i%MOD;

    for(int i=;i<=n;i++)fav[i]=inv(fac[i],MOD);

    p[]=f[]=;

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

        p[i]=fac[i]*inv2%MOD;

        if(i>&&i%)p[i]=(p[i]+fac[i-]*inv2)%MOD;

        for(int j=;j<=i;j++)f[i]=(f[i]+p[j]*f[i-j]%MOD*C(i-,j-))%MOD;

    }

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

    return ;

}

巴特西

【STSRM10】数学上来先打表

最新文章

热门文章