問題：含有兩邊分别為 n 和 m 個不同的點的連通二分圖有多少種，即同構的圖算是多個。
記 含有 n , m 個點的連通圖個數為 F[n][m] ；
含有 n , m 個點的不連通圖個數為 G[n][m] ；
含有 n , m 個點的圖的個數為 H[n][m] = 2^(n*m) ；
有 F[n][m] + G[n][m] = H[n][m] ； F[n][m] = H[n][m] - G[n][m] ；
是以要求 F[n][m] 隻需求 G[n][m] ；
求 G[n][m] ：枚舉 1 号點所在的連通塊大小為 k1 ( 1 ~ n ) + k2 ( 0 ~ m ) 且 k1、k2 不能同時取最大值；
當 1 号點所在連通塊大小為 k1+k2 時： k1個點選取情況為組合數 C[n-1][k1-1]
k2個點選取情況為組合數 C[m][k2]
該連通塊的種類數确定 k1+k2 個點後，連通塊的種類數為 F[k1][k2]
剩餘 n-k1 + m-k2 個點組成的圖的種類數 H[n-k1][m-k2]
是以情況數為 C[n-1][k1-1] * C[m][k2] * F[k1][k2] * H[n-k1][m-k2]
G[n]為所有枚舉的情況數總和
定初始值 F[0][0] = F[0][1] = F[1][0] = 1 ， 其餘有一維是 0 時 F 值為 0
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 #include<math.h>
5 using namespace std;
6 typedef long long ll;
7
8 const int maxn=55;
9 const int maxm=55;
10 const int mod=1e9+7;
11
12 ll C[maxn][maxn]; //組合數
13 ll F[maxn][maxm],G[maxn][maxm],H[maxn][maxm];
14
15 ll QP(ll a,ll n){ //快速幂
16 ll tmp=a,ans=1;
17 while(n){
18 if(n&1)ans=ans*tmp%mod;
19 tmp=tmp*tmp%mod;
20 n>>=1;
21 }
22 return ans;
23 }
24
25 void init(){
26 for(int i=0;i<maxn;++i){
27 for(int j=0;j<maxm;++j){
28 H[i][j]=QP(2,i*j);
29 }
30 }
31 for(int i=0;i<maxn;++i){
32 for(int j=0;j<=i;++j){
33 C[i][j]=(i&&j)?(C[i-1][j]+C[i-1][j-1])%mod:1;
34 }
35 }
36 F[0][0]=F[1][0]=F[1][0]=1;
37 for(int i=2;i<maxn;++i)F[i][0]=0;
38 for(int i=2;i<maxm;++i)F[0][i]=0;
39 for(int i=1;i<maxn;++i){
40 for(int j=1;j<maxm;++j){
41 G[i][j]=0;
42 for(int k1=1;k1<=i;++k1){
43 for(int k2=0;k2<=j;++k2){
44 if(k1==i&&k2==j)continue;
45 G[i][j]+=C[i-1][k1-1]*C[j][k2]%mod*F[k1][k2]%mod*H[i-k1][j-k2]%mod;
46 G[i][j]%=mod;
47 }
48 }
49 F[i][j]=((H[i][j]-G[i][j])%mod+mod)%mod;
50 }
51 }
52 } 轉載于:https://www.cnblogs.com/cenariusxz/p/5688549.html