Loj 6389 好图计数

Posted on | Views:

生成函数.

对于一张连通的图,若它的补图也是连通图,根据定义,当 $n>1$ 时,它们都不是好图.而不连通的图的补图一定是连通的,于是可以得出,当 $n>1​$ 时,连通好图和不连通好图是可以用补图关系一一对应的,两者数目相等.

设 $f_i$ 表示 $i$ 个点的好图的数目, $g_i$ 表示 $i$ 个点连通好图的数目,则有 $f_0=f_1=g_1=1,f_i=2\cdot g_i(i>1)$ .

考虑 $f_i$ 的生成函数 $F(x)$ ,枚举大小为 $k​$ 的连通块数目,在无标号下可以得出
$$
F=\prod_{k\ge 1}(1-x^k)^{-g_k}\\
\ln(F)=\sum_{k\ge 1}-g_k\cdot \ln(1-x^k) \\
\frac{F’}{F}=\sum_{k\ge 1} g_k\cdot \frac{kx^{k-1}}{1-x^k}\\
[x^n]F’=[x^n] (F\cdot \sum_{k\ge 1} g_k\cdot \frac{kx^{k-1}}{1-x^k})\\
(n+1)f_{n+1}=\sum_{i=0}^n f_i\cdot [x^{n-i}]\sum_{k\ge1} g_k\cdot \frac{kx^{k-1}}{1-x^k}\\
(n+1)f_{n+1}=\sum_{i=0}^n f_i\cdot\sum_{k\ge 1,k|n-i+1}g_k\cdot k\\
\frac{n+1} 2f_{n+1}=\sum_{i=0}^n f_i\cdot\sum_{1\le k<n+1,k|n-i+1}g_k\cdot k
$$
依次枚举 $n$ ,过程中暴力维护每个 $\sum g_k\cdot k$ ,时间复杂度 $O(n^2)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define y1 ysgh
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
int T, P;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
typedef unsigned long long ull;
const ull bound = 1ULL << 62;
const int N = 23333 + 10;
int m = 23333, inv[N], f[N], g[N], h[N];
void upd(int k)
{
	int val = mul(k, g[k]);
	for (int i = k; i <= m; i += k)
		inc(h[i], val);
}
int main()
{
	T = read(), P = read();
	f[0] = f[1] = g[1] = inv[1] = 1;
	upd(1);
	for (int n = 1; n < m; ++n)
	{
		ull tmp = 0;
		for (int i = 0; i <= n; ++i)
		{
			tmp += 1ULL * f[i] * h[n - i + 1];
			if (tmp > bound)
				tmp %= P;
		}
		inv[n + 1] = mul(P - P / (n + 1), inv[P % (n + 1)]);
		g[n + 1] = mul(tmp % P, inv[n + 1]);
		f[n + 1] = add(g[n + 1], g[n + 1]);
		upd(n + 1);
	}
	while (T--)
		write(f[read()], '\n');
	return 0;
}