bzoj3456 城市规划多项式求In

\(n\)个点的无向联通图的个数

打着好累啊

一定要封装一个板子

记\(C(x)\)为无向图个数的指数型生成函数，\(C(0) = 1\)

记\(G(x)\)为无向联通图个数的指数型生成函数，\(G(0) = 0\)

那么\(G(x) = e^{C(x)}\)

从而，\(C(x) = In(G(x))\)

复杂度\(O(n \log n)\)

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ri register int

#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

const int sid = 270000;

const int mod = 1004535809;

inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; }

inline int Dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; }

inline int mul(int a, int b) { return 1ll * a * b % mod; }

inline int fp(int a, int k) {

	int ret = 1;

	for( ; k; k >>= 1, a = mul(a, a))

		if(k & 1) ret = mul(ret, a);

	return ret;

}

int N_, N, n, lg;

int ans[sid], ivfac[sid], fac[sid], inv[sid], rev[sid];

inline void init(int Maxn, int &rn, int &rlg, int opt = 0) {

	rn = 1; rlg = 0;

	while(rn < Maxn) rn <<= 1, rlg ++;

	if(opt) rep(i, 0, rn) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (rlg - 1));

}

inline int NTT(int *a, int n, int opt) {

	for(ri i = 0; i < n; i ++)

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

	for(ri i = 1; i < n; i <<= 1)

	for(ri j = 0, g = fp(3, (mod - 1) / (i << 1)); j < n; j += (i << 1))

	for(ri k = j, G = 1; k < i + j; k ++, G = 1ll * G * g % mod) {

		int x = a[k], y = mul(G, a[i + k]);

		a[k] = (x + y >= mod) ? x + y - mod : x + y;

		a[i + k] = (x - y < 0) ? x - y + mod : x - y;

	}

	if(opt == -1) {

		reverse(a + 1, a + n);

		for(ri i = 0; i < n; i ++) a[i] = mul(a[i], inv[n]);

	}

}

int iva[sid], ivb[sid];

inline void get_inv(int *a, int n, int *ret) {

	if(n == 1) { ret[0] = inv[a[0]]; return; }

	get_inv(a, n >> 1, ret);

	init(n + n, N, lg, 1);

	for(ri i = 0; i < N; i ++) iva[i] = ivb[i] = 0;

	for(ri i = 0; i < n; i ++) iva[i] = a[i], ivb[i] = ret[i];

	NTT(iva, N, 1); NTT(ivb, N, 1);

	for(ri i = 0; i < N; i ++) iva[i] = Dec(Inc(ivb[i], ivb[i]), mul(iva[i], mul(ivb[i], ivb[i])));

	NTT(iva, N, -1);

	for(ri i = 0; i < n; i ++) ret[i] = iva[i];

}

inline void wf(int *a, int n, int *ret) { for(ri i = 1; i < n; i ++) ret[i - 1] = mul(a[i], i); }

inline void jf(int *a, int n, int *ret) { for(ri i = 1; i < n; i ++) ret[i] = mul(a[i - 1], inv[i]); }

int ivf[sid], df[sid];

inline void get_ln(int *a, int n, int *ret) {

	int N = 1, lg = 0;

	init(n + n, N, lg);

	wf(a, n, df); get_inv(a, n, ivf);

	init(n + n, N, lg, 1);

	NTT(df, N, 1); NTT(ivf, N, 1);

	for(ri i = 0; i < N; i ++) df[i] = mul(df[i], ivf[i]);

	NTT(df, N, -1); jf(df, n, ret);

}

int C2[sid], f[sid];

int main() {

	freopen("3456.in", "r", stdin);

	freopen("3456.out", "w", stdout);

	cin >> n;

	init(n + 5, N_, lg);

	N_ <<= 1;

	inv[0] = inv[1] = 1;

	fac[0] = fac[1] = 1;

	ivfac[0] = ivfac[1] = 1;

	rep(i, 2, N_) {

		fac[i] = mul(fac[i - 1], i);

		inv[i] = mul(inv[mod % i], mod - mod / i);

	}

	rep(i, 2, N_) ivfac[i] = mul(inv[i], ivfac[i - 1]);

	rep(i, 0, N_) C2[i] = 1ll * i * (i - 1) / 2 % (mod - 1);

	rep(i, 0, N_) f[i] = mul(fp(2, C2[i]), ivfac[i]);

	N_ >>= 1;

	get_ln(f, N_, ans);

	printf("%d\n", mul(ans[n], fac[n]));

	return 0;

}

巴特西

bzoj3456 城市规划多项式求In

最新文章

热门文章

巴特西

bzoj3456 城市规划 多项式求In

最新文章

热门文章

bzoj3456 城市规划多项式求In