Lflame

【2016/4/25 考题】Graph 递推

    题意:求 n 个点带标号的边权为[1,m]的不同二分图的个数,对一个质数取模。注意此处的不同是指边集不同或某条边的权值不同。(题意经稍稍简化,原题需要特判 n==1 的情况)


    再次Orz  ....   这种题或许还是该再多写写 ....

    令 ans[i] 表示 i 个点的答案,递推时考虑一个常用的方法,即枚举最后点 i 放入的连通块的大小。

    于是 ans[i]=sigma{ C(i-1,j)*f[j+1]*ans[i-j-1]  , 0<=j<=i-1 },其中 f[i] 表示 i 个点的连通的二分图的个数。

    现在问题转化为怎么求 f[i],考虑补集转化,令 g[i] 表示 i 个点黑白染色后再随意连边的方案数(所有点均反色后算同一种方案)。

    则 g[i]=1/2 * sigma{ C(i,j)*(m+1)^((i-j)*j) ,  0<=j<=i } ,即枚举选哪些点染黑,然后边权随便选,边权为 0 看作不存在这条边。

    考虑从 g[i] 中减去所有不连通的方案即为 f[i],要减去的东西为:

    sigma{ C(i-1,j) * 2 * f[j+1] * g[i-j-1] ,  0<=j<=i-2 }   , 注意 j+1 是小于 i 的。为什么呢 ? 同样考虑枚举第 i 个点加入的连通块大小,连通块需要连通,所以为 f[j+1],而剩余点怎么连都无所谓,即为 g[i-j-1]。乘 2 是因为枚举的这个连通块与块外部其中一个,交换 x 部与 y 部后,会在 g[] 中视为不同的方案。


    于是先递推出 g[] , 再递推出 f[] ,再递推出 ans[] 即可。

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;


const int MOD=105225319 ;


long long pow_mod(long long a,long long b){

long long ret=1 ;

while(b){

if(b&1)ret=ret*a%MOD ;

a=a*a%MOD , b>>=1 ;

}

return ret;

}


int n,m ;

long long ci[1000005],jc[1005],rev_jc[1005] ;

long long ans[1005] , f[1005] , g[1005] , rev_2 ;


long long C(long long a,long long b){ return jc[a]*rev_jc[b]%MOD*rev_jc[a-b]%MOD ; }


void init(){

ci[0]=jc[0]=rev_jc[0]=1 , rev_2=pow_mod(2,MOD-2) ;

for(int i=1;i<=1000000;++i)ci[i]=ci[i-1]*(m+1)%MOD ;

for(int i=1;i<=1000;++i) jc[i]=jc[i-1]*i%MOD , rev_jc[i]=pow_mod(jc[i],MOD-2) ;

}


void solve()

{

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

for(int j=0;j<=i;++j)g[i]=(g[i]+C(i,j)*ci[(i-j)*j])%MOD ;

g[i]=g[i]*rev_2%MOD ;

}

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

f[i]=g[i] ;

for(int j=0;j<=i-2;++j) {

f[i]=(f[i]-C(i-1,j)*2*f[j+1]%MOD*g[i-j-1]%MOD) ;

if(f[i]<0)f[i]+=MOD ;

if(f[i]>=MOD)f[i]-=MOD ;

}

}

ans[1]=ans[0]=1 ;

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

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

}

printf("%lld\n",ans[n]) ;

}


int main()

{

freopen("graph.in","r",stdin) ;

freopen("graph.out","w",stdout) ;

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

if(n==1){

printf("0\n") ;

return 0 ;

}

init() ;

solve() ;

return 0 ;

}


评论