【算法】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
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=2010,MOD=1004535809;ll inv2=(MOD+1)/2;ll n,fac[maxn],f[maxn],p[maxn],fav[maxn];void exgcd(ll a,ll b,ll &x,ll &y){
     if(!b){x=1;y=0;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[0]=p[0]=fac[0]=fav[0]=1;    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%MOD;    for(int i=1;i<=n;i++)fav[i]=inv(fac[i],MOD);    p[1]=f[1]=1;    for(int i=2;i<=n;i++){        p[i]=fac[i]*inv2%MOD;        if(i>3&&i%3)p[i]=(p[i]+fac[i-1]*inv2)%MOD;        for(int j=1;j<=i;j++)f[i]=(f[i]+p[j]*f[i-j]%MOD*C(i-1,j-1))%MOD;    }    printf("%lld",f[n]);    return 0;}