Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js
Petrozavodsk Summer-2014. Andrew Stankevich Contest 46. B.Bipartite Bicolored Graphs

Petrozavodsk Summer-2014. Andrew Stankevich Contest 46. B.Bipartite Bicolored Graphs

题目大意

有一个 n 个点的二分图,每条边有黑边和白边两种,问有多少这样的二分图。

题目分析

考虑到所有的连点可能会组成若干个集合,因此先考虑求出两个分别为 ij 个点的集合能构成多少个联通的二分图,令其为 g[i][j]。正向推显然又要考虑连通性,因此可以考虑反过来求多少个二分图不连通。首先可以求得 ij 个点能够成多少个题意中所说的有黑白两种边的二分图。显然答案为 \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}。即可求得答案

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据