POJ1737 连通图

一句话题意：求一个 \(n\) 点带编号的连通图数量。

吐槽一下：好好一道计数 dp 为什么不加取余？？？？逼着选手写高精度的出题人应该拎出去烧……哦楼天城是出题人是吧哦当我没说我什么都没说我现在就把我拎出去 QAQ

这道题就很计数 dp 那个味对吧，所以设 \(f_i\) 为 \(i\) 个点的连通图数量。

但这样非常难算，你想我们数数 dp 是围绕一个基准，按照这个基准来划分子问题，一个连通图拿什么当基准？正难则反，考虑计算不连通图的数量，因为这样每一个连通块就自然而然给了我们划分出来子问题的空间了。我们记 \(g_i\) 为 \(i\) 个点非连通图数量。以下为了叙述方便我们令 \(b2_{i} = 2^{(i - 1)i / 2}\)，放在这题的含义就是：有 \(i\) 个点共能产生多少张图。

我们先考虑 1 号点，以 1 号点所在连通块大小作为我们划分的基准，这样就分成了一些子问题了。我们令一号店所在连通块大小为 \(k\)，也就是说除了 \(1\) 点外要选 \((k - 1)\) 个点。这样的连通块一共有 \(C_{n - 1}^{k - 1}\) 种。连通块内部有 \(f(k)\) 种方案。连通块外部呢？管它的，随便它们联通不联通，反正只要不和我们选出来的 \((k - 1)\) 个点和 \(1\) 连边就好了。所以答案就是 \(g_{x} = \sum\limits_{k = 1}^{x - 1}C_{x - 1}^{k - 1}f_xb2_{x - k}, f_x = b2_{x} - g_{x}\)

毒瘤就毒瘤在写高精度，这玩意儿就算是暴力都好久没写了，很担心自己哪里细节写挂了，反正高精度打了七八十来行，高兴极了

//SIXIANG

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#define MAXN 100000

#define QWQ cout << "QWQ" << endl;

using namespace std;

struct Bignum {

	string num;

	Bignum operator + (const Bignum &other) const {

		string s1 = num, s2 = other.num, rest = "";

		if(s1.size() < s2.size()) swap(s1, s2);

		while(s2.size() < s1.size()) s2 = "0" + s2;

		reverse(s1.begin(), s1.end());

		reverse(s2.begin(), s2.end());

		int len = s1.size(), a = 0, b = 0, c = 0, d = 0;

		for(int p = 0; p < len; p++) {

			a = s1[p] - '0', b = s2[p] - '0';

			c = (a + b + d) % 10, d = (a + b + d) / 10;

			rest += char(c + '0');

		}

		if(d) rest += char(d + '0');

		reverse(rest.begin(), rest.end());

		string ans = "";

		bool lead = 0;

		for(int p = 0; p < rest.size(); p++) {

			if(!lead)

				if(rest[p] != '0')

					lead = 1;

			if(lead)

				ans += rest[p];

		}

		return (Bignum){ans};

	}

	Bignum operator - (const Bignum &other) const {

		string s1 = num, s2 = other.num;

		while(s2.size() < s1.size()) s2 = "0" + s2;

		reverse(s1.begin(), s1.end());

		reverse(s2.begin(), s2.end());

		int a = 0, b = 0, c = 0, d = 0;

		string rest = "", ans = "";

		for(int p = 0; p < s1.size(); p++) {

			a = s1[p] - '0', b = s2[p] - '0';

			c = a + d - b;

			if(c < 0) c += 10, d = -1;

			else d = 0;

			rest += char(c + '0');

		}

		bool lead = 0;

		for(int p = rest.size() - 1; p >= 0; p--) {

			if(!lead)

				if(rest[p] != '0')

					lead = 1;

			if(lead)

				ans += rest[p];

		}

		return (Bignum){ans};

	}

	Bignum operator * (const Bignum &other) const {

		string s1 = num, s2 = other.num;

		reverse(s1.begin(), s1.end());

		reverse(s2.begin(), s2.end());

		int a[5010], b[5010], c[10010];

		memset(a, 0, sizeof(a));

		memset(b, 0, sizeof(b));

		memset(c, 0, sizeof(c));

		int len1 = s1.size(), len2 = s2.size();

		for(int p = 0; p < len1; p++)

			a[p] = s1[p] - '0';

		for(int p = 0; p < len2; p++)

			b[p] = s2[p] - '0';

		for(int p = 0; p < len1; p++)

			for(int i = 0; i < len2; i++)

				c[p + i] += a[p] * b[i];

		for(int p = 0; p <= len1 + len2; p++)

			c[p + 1] += c[p] / 10, c[p] %= 10;

		bool lead = 0;

		string rest = "";

		for(int p = len1 + len2 + 1; p >= 0; p--) {

			if(!lead)

				if(c[p] != 0)

					lead = 1;

			if(lead)

				rest += char(c[p] + '0');

		}

		return (Bignum){rest};

	}

};

Bignum b2[1260], C[60][60], f[260], g[260];

int n;

int id(int n) {return n * (n - 1) / 2;}

void prepare() {

	b2[0].num = "1";

	for(int p = 1; p <= 1250; p++)

		b2[p] = b2[p - 1] * (Bignum){"2"};

	for(int p = 0; p <= 55; p++)

		for(int i = 0; i <= 55; i++)

			C[p][i].num = "0";

	C[0][0].num = C[1][0].num = C[1][1].num = "1";

	for(int p = 2; p <= 55; p++) {

		C[p][0].num = "1";

		for(int i = 1; i <= p; i++)

			C[p][i] = C[p - 1][i - 1] + C[p - 1][i];

	} 

	f[1].num = "1", g[1].num = "0";

	for(int p = 2; p <= 55; p++)

		f[p].num = g[p].num = "0";

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

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

			Bignum tmp = C[i - 1][k - 1] * f[k] * b2[id(i - k)];

			g[i] = g[i] + tmp;

		}

		f[i] = b2[id(i)] - g[i];

	}

}

int init() {

	cin >> n;

	if(!n) return -1;

	cout << f[n].num << endl;

}

int main() {

	prepare();

	while(1)

		if(init() < 0) return 0;

}

巴特西

POJ1737 连通图

最新文章

热门文章