Petrozavodsk Summer-2014. Andrew Stankevich Contest 46. B.Bipartite Bicolored Graphs
题目大意
有一个 $n$ 个点的二分图，每条边有黑边和白边两种，问有多少这样的二分图。
题目分析
考虑到所有的连点可能会组成若干个集合，因此先考虑求出两个分别为 $i$ 和 $j$ 个点的集合能构成多少个联通的二分图，令其为 $g[i][j]$。正向推显然又要考虑连通性，因此可以考虑反过来求多少个二分图不连通。首先可以求得 $i$ 和 $j$ 个点能够成多少个题意中所说的有黑白两种边的二分图。显然答案为 $\sum\limits_{k = 0} ^ {i \cdot j} C_{i \cdot j} ^ {k} \cdot 2 ^ k = 3 ^ {i \cdot j}$ 。为了保证不重复计算，可以固定其中一个集合中的一个点，则有应当去掉的有 $\sum\limits_{k=1} ^ {i} \sum\limits_{l=0} ^ {j} g[k][l] \cdot C_{i – 1}^{k – 1} \cdot C_{j}^{l} \cdot 3 ^ {(i – k) \cdot (j – l)}$
求完 $g$ 数组之后，考虑定义 $f[i]$ 为 $i$ 个点的答案。那么可以考虑加入最后一个点，那么就有 $f[i] = \sum\limits_{j=0}^{i-1}\sum\limits_{k=0}^{i-k-1} f[i – j – k – 1] \cdot g[j + 1][k] \cdot C_{i – 1}^{j} \cdot C_{i – j – 1}^{k}$。即可求得答案
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
long long mod = 175781251;
int t, n, m;
long long f[105];
long long g[105][105];
long long c[105][105];
long long th[10005];
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = ret * b % mod;
}
b = b * b % mod;
x >>= 1;
}
return ret;
}
int main(){
int i, j, k, l;
c[0][0] = 1;
for(i=1;i<=100;i++){
c[i][0] = 1;
for(j=1;j<=i;j++){
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
th[0] = 1;
for(i=1;i<=10000;i++){
th[i] = th[i - 1] * 3ll % mod;
}
for(i=0;i<=100;i++){
for(j=0;i+j<=100;j++){
g[i][j] = th[i * j];
for(k=1;k<=i;k++){
for(l=0;l<=j;l++){
if((k == i and j == l)){
continue;
}
g[i][j] -= c[i - 1][k - 1] * c[j][l] % mod * g[k][l] % mod * th[(i - k) * (j - l)] % mod;
g[i][j] = (g[i][j] % mod + mod) % mod;
}
}
}
}
f[0] = 1;
for(i=1;i<=100;i++){
for(j=0;j<i;j++){
for(k=0;k+j<i;k++){
f[i] += f[i - j - k - 1] * g[j + 1][k] % mod * c[i - 1][j] % mod * c[i - j - 1][k] % mod;
f[i] %= mod;
}
}
}
while(~scanf("%d", &n) and n){
printf("%lld\n", f[n]);
}
return 0;
}