Loj 6402 yww 与校门外的树

Posted on | Views:

多项式求逆.

首先这个随机过程可以等价于随机出了一个 $1\sim n$ 的排列,需要对每个排列的答案求和.

不难发现,各个连通块是一段连续的区间,且两个相邻的连通块之间一定是左侧的最小值大于右侧的最大值.

设 $F(x)$ 表示长度为 $i$ 的排列形成一个连通块的 OGF, 若干个这样的结构会组合成一个排列,且合并时顺序固定.

那么设 $P(x)=\sum i!x^i​$ ,则有 $\frac{1}{1-F}=P​$ ,得出 $F=1-\frac{1}{P}​$ .

考虑如何计算答案,只需要把贡献放入 $F​$ 的每一项中,再用若干个结构卷起来组合成排列即可.

设 $G=\sum [x^i]F\cdot i\cdot x^i$ ,则 $[x^n]\frac{1}{1-G}$ 即为所求.

需要实现多项式乘法及求逆,时间复杂度 $O(n\log n)$ .

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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);
}
const int P = 998244353, G = 3;
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;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 1 << 20 | 10;
int curn = 0, rev[N], omega[N], inv[N];
void init(int n)
{
	if (n == curn)	
		return;
	for (int i = 0; i < n; ++i)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));
	for (int l = 2; l <= n; l <<= 1)
	{
		omega[l] = fpow(G, (P - 1) / l);
		inv[l] = fpow(omega[l], P - 2);
	}
	curn = n;
}
void DFT(int *a, int n, bool invflag)
{
	init(n);
	for (int i = 0; i < n; ++i)
		if (i < rev[i])
			swap(a[i], a[rev[i]]);
	for (int l = 2; l <= n; l <<= 1)
	{
		int gi = omega[l], m = l >> 1;
		if (invflag)
			gi = inv[l];
		for (int *p = a; p != a + n; p += l)
		{
			int g = 1;
			for (int i = 0; i < m; ++i)
			{
				int t = mul(g, p[i + m]);
				p[i + m] = add(p[i], P - t);
				p[i] = add(p[i], t);
				g = mul(g, gi);
			}
		}
	}
	if (invflag)
	{
		int invn = fpow(n, P - 2);
		for (int i = 0; i < n; ++i)
			a[i] = mul(a[i], invn);
	}
}
void NTT(int *A, int *B, int *C, int lenA, int lenB)
{
	int lenC = lenA + lenB - 1, n = 1;
	while (n < lenC)
		n <<= 1;
	static int a[N], b[N];
	for (int i = 0; i < lenA; ++i)
		a[i] = A[i];
	for (int i = lenA; i < n; ++i)
		a[i] = 0;
	for (int i = 0; i < lenB; ++i)
		b[i] = B[i];
	for (int i = lenB; i < n; ++i)
		b[i] = 0;
	DFT(a, n, false);
	DFT(b, n, false);
	for (int i = 0; i < n; ++i)
		C[i] = mul(a[i], b[i]);
	DFT(C, n, true);
}
void Inverse(int *A, int *B, int len)
{
	int n = 1;
	while (n < len)
		n <<= 1;
	static int res[N], tmp[N];
	res[0] = fpow(A[0], P - 2);
	for (int i = 2; i <= n; i <<= 1)
	{
		NTT(A, res, tmp, i, i);
		for (int j = 0; j < i; ++j)
			tmp[j] = add(0, P - tmp[j]);
		inc(tmp[0], 2);
		NTT(res, tmp, res, i, i);
	}
	for (int i = 0; i < len; ++i)
		B[i] = res[i];
}
int n, F[N];
int main()
{
	n = read();
	int fac = 1;
	for (int i = 0; i <= n; ++i)
	{
		F[i] = fac;
		fac = mul(fac, i + 1);
	}
	Inverse(F, F, n + 1);
	for (int i = 0; i <= n; ++i)
		F[i] = add(0, P - F[i]);
	inc(F[0], 1);
	for (int i = 0; i <= n; ++i)
		F[i] = add(0, P - mul(i, F[i]));
	inc(F[0], 1);	
	Inverse(F, F, n + 1);
	write(F[n], '\n');
	return 0;
}