【BZOJ3456】城市规划

题目

思路&算法

我们设点数为\(n\)的简单图的数量为\(f_n\)，点数为\(n\)的简单连通图有\(g_i\)个

于是我们知道，从\(n\)个点中选\(2\)个点有\(n \choose 2\)种选法，而对于两个点可以连边或不连，于是\(f_n = 2^{n \choose 2}\)

同时， \(f_n\)还满足\(f_n = \sum\limits_{i = 1}^{n}{n-1 \choose {i-1}}g_if_{n-i}\)，因为我们可以考虑钦定某一点为联通块中的一点，然后从剩余的点中找\(i-1\)个点，练成一个联通块，剩下随便，然后\(i\)取遍\(1 \sim n\)中的所有数后的和为\(f_n\)。

于是，我们来愉快的推式子

\[2^{n \choose 2} = \sum_{i = 1}^{n}{{n-1} \choose {i-1}}g_if_{n-i}
\]

把\(f_n = 2^{n \choose 2}\)带入

\[\begin{align*}
2^{n \choose 2} &= \sum_{i = 1}^{n}{{n-1} \choose {i-1}}2^{{n-i\;} \choose {2}}g_i\\
2^{n \choose 2} &= \sum_{i = 1}^{n}\frac{{(n-1)!}/{(i-1)!}}{(n-i)!}g_i2^{{n-i\;} \choose 2}\\
2^{n \choose 2} &= \sum_{i = 1}^{n}\frac{{(n-1)!}}{(n-i)!(i-1)!}g_i2^{{n-i\;} \choose {2}}\\
2^{n \choose 2} &= (n-1)!\sum_{i = 1}^{n}\frac{1}{(i-1)!(n-i)!}g_i2^{{n-i\;} \choose {2}}\\
\frac{2^{{n} \choose 2}}{(n-1)!} &= \sum_{i=1}^{n}\frac{1}{(n-i)!(n-1)!}g_i2^{{n-i\;} \choose {2}}\\
\frac{2^{{n} \choose 2}}{(n-1)!} &= \sum_{i=1}^{n} \left(\frac{1}{n-i}2^{{n-i\;} \choose {2}}\right)\left(\frac{1}{(i-1)!}g_i\right)
\end{align*}
\]

这是一个卷积

我们令

\(A(x) = \sum\limits_{i = 1}^{n}\frac{1}{(i-1)!}2^{i \choose 2}x^i\)， \(B(x) = \sum\limits_{i = 1}^{n}\frac{1}{(i-1)!}g_{i-1}x^i\)， \(C(x) = \sum\limits_{i = 0}^{n-1}\frac{1}{i!}2^{i \choose 2}x^i\)

于是\(C(x) = A(x)B(x)\)

然后\(B(x) = A(x)C^{-1}(x)\)

代码

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 520010;

const LL mod = 1004535809LL;

inline LL power(LL a, LL n, LL mod)

{	LL Ans = 1;

	a %= mod;

	while (n)

	{	if (n & 1) Ans = (Ans * a) % mod;

		a = (a * a) % mod;

		n >>= 1;

	}

	return Ans;

}

struct Mul

{	int rev[N];

	int Len, Bit;

	LL wn[N];

	void getReverse()

	{	for (int i = 0; i < Len; i++)

			rev[i] = (rev[i>>1] >> 1) | ((i&1) * (Len >> 1));

	}

	void NTT(LL * a, int opt)

	{	getReverse();

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

			if (i < rev[i]) swap(a[i], a[rev[i]]);

		int cnt = 0;

		for (int i = 2; i <= Len; i <<= 1)

		{	cnt++;

			for (int j = 0; j < Len; j += i)

			{	LL w = 1LL;

				for (int k = 0; k < (i>>1); k++)

				{	LL x = a[j + k];

					LL y = (w * a[j + k + (i>>1)]) % mod;

					a[j + k] = (x + y) % mod;

					a[j + k + (i>>1)] = (x - y + mod) % mod;

					w = (w * wn[cnt]) % mod;

				}

			}

		}

		if (opt == -1)

		{	reverse(a + 1, a + Len);

			LL num = power(Len, mod-2, mod);

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

				a[i] = (a[i] * num) % mod;

		}

	}

	void getLen(int l)

	{	Len = 1, Bit = 0;

		for (; Len <= l; Len <<= 1) Bit++;

	}

	void init()

	{	for (int i = 0; i < 22; i++)

			wn[i] = power(3, (mod-1) / (1LL << i), mod);

	}

} Calc;

LL tmp1[N], tmp2[N];

void cpy(LL * A, LL * B, int len1, int len2)

{	for (int i = 0; i < len1; i++) A[i] = B[i];

	for (int i = len1; i < len2; i++) A[i] = 0;

}

void getInv(LL * A, LL * B, int Len)

{	B[0] = power(A[0], mod-2, mod);

	for (register int i = 2; i <= Len; i <<= 1)

	{	int l = i << 1;

		cpy(tmp1, A, i, l);

		cpy(tmp2, B, i>>1, l);

		Calc.Len = l;

		Calc.NTT(tmp1, 1);

		Calc.NTT(tmp2, 1);

		for (register int j = 0; j < l; j++)

			tmp1[j] = ((2LL * tmp2[j]) % mod + mod - ((tmp2[j] * tmp2[j]) % mod * tmp1[j]) % mod) % mod;

		Calc.NTT(tmp1, -1);

		for (register int j = 0; j < i; j++)

			B[j] = tmp1[j];

	}

}

LL A[N], B[N], Ans[N];

LL fac[N];

int main()

{	int n;

	scanf("%d", &n);

	fac[0] = 1;

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

		fac[i] = (fac[i-1] * (LL) i) % mod;

	Calc.getLen(n);

	int len = Calc.Len;

	Calc.init();

	A[0] = 1;

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

		A[i] = (power(2LL, (LL) i * (LL) (i-1) / 2LL, mod) * power(fac[i], mod-2, mod)) % mod;

	B[0] = 0;

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

		B[i] = (power(2LL, (LL) i * (LL) (i-1) / 2LL, mod) * power(fac[i-1], mod-2, mod)) % mod;

	getInv(A, Ans, len);

	Calc.Len = len << 1;

	Calc.NTT(Ans, 1);

	Calc.NTT(B, 1);

	for (int i = 0; i < Calc.Len; i++)

		Ans[i] = (Ans[i] * B[i]) % mod;

	Calc.NTT(Ans, -1);

	printf("%lld\n", (Ans[n] * fac[n-1]) % mod);

	return 0;

}

巴特西

【BZOJ3456】城市规划

题目

思路&算法

代码

最新文章

热门文章