好了，又是爆零的一天，恭喜我自己

$\text{score：0 + 0 + 0 = 0 rk：27/27}$

Problem A：小卖部

题目描述

ysgh 是一名数数大师。

现在小卖部有 $n$ 种商品，第 $i$ 种有 $a_i$ 个，价格为 $b_i$。

ysgh 总共去了 $Q$ 天小卖部，第 $i$ 天他只会购买编号在 $l_i \sim r_i$ 的商品。他的卡里有 $c_i$ 元，因此他只能购买价值和不超过 $c_i$ 元的物品。

ysgh 想要知道有多少种购买物品的方案。由于答案很大，你只需要输出答案对 $1000000007$ 取模后的结果。两种方案被认为是不同的当且仅当存在一种物品，其购买数量不同。

当然，ysgh玩了个小花招，你需要通过上一个询问的答案来推导下一个询问的参数。

数据范围

对于所有测试数据，满足 $1 \le n \le 10000, ~ 1 \le Q \le 50000, ~ 1 \le a_i, b_i, c_i \le 1000, 1 \le l’_i, r’_i \le n$

题解

令 $C = 1000$

首先看得出来可以用生成函数搞，显然答案为 $F_i(x) = \prod\limits_{i = 1}^n \left(\sum\limits_{k = 0}^{a_i}x^{k \times b_i}\right)$

对 $F(x)$ 求个前缀和 $SF_n (x)$，并设 $SF_n(x)$ 逆元为 $I_n(x)$，答案就是 $SF_r(x)I_{l - 1}(x)$ 的前 $c$ 项系数和

然后我就开始 $FFT$、多项式求逆什么的乱搞，时间爆炸，然后爆零（虽然我连每次询问的 $l, r$ 都算错了）

好吧实际上上面那玩意儿继续化，可以变成 $F_i(x) = \frac{1 - x^{(a_i + 1)b_i}}{1 - x^{b_i}}$

接下来的步骤我觉着很有意思

首先把分子分母分开，就变成 $F_i(x) = (1 + x^{b_i} + x^{2b_i} + …)(1 - x^{(a_i + 1)b_i})$

假设现在要处理 $SF_i(x) = SF_{i - 1}(x)F_i(x)$，那么设 $SF_i(X), SF_{i - 1}(x)$ 的第 $k$ 项分别为 $g_k, f_k$，则有 $g_k = f_k + f_{k - b_i} + f_{k - 2b_i} + …$（乘 $F(x)$ 前半部分），然后 $g_k = g_k - g_{k - (a_i + 1)b_i}$（乘 $F(x)$ 后半部分），记得第二部分要倒推

接下来只需处理逆元，先直接 $O (C^2)$ 求出 $I_{n}(x)$，然后 $I_i(x) = I_{i + 1}(x)F_{i + 1}(x)$ 处理即可

还有一部处理，假设得到的最终多项式 $A(x) = SF_r(x)I_{l - 1}(x)$，然后要求 $\sum\limits_{i = 0}^cA(x)[x^i]$，这样还是需要一次多项式乘法，时间还是不行

此时可以令 $B(x) = \frac{A(x)}{1 - x} = A(x)(1 + x + x^2 + …)$，那么 $\sum\limits_{i = 0}^cA(x)[x^i] = B(x)[x^c]$，就可以 $O (C)$ 处理

说实话我觉得这些处理是真挺厉害的（但我觉得只是因为我太菜了）

时间复杂度 $O \left((n + Q)C\right)$

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MOD 1000000007

using namespace std;

const int MAXN = 1e04 + 10;
const int MAXC = 1000 + 10;

int C = 1000;

inline int power (int x, int p) {
	int cnt = 1;
	while (p) {
		if (p & 1) cnt = 1ll * cnt * x % MOD;
		x = 1ll * x * x % MOD, p >>= 1;
	}
	return cnt;
}

int N, Q;
int a[MAXN], b[MAXN];

void mul (int* A, int* B, int p) {
	for (int i = 0; i <= C; i ++) A[i] = (B[i] + (i >= b[p] ? A[i - b[p]] : 0)) % MOD;
	for (int i = C; i >= (a[p] + 1) * b[p]; i --)
		A[i] = (A[i] - A[i - (a[p] + 1) * b[p]] + MOD) % MOD;
}
void inverse (int* A, int* inv) {
	inv[0] = 1;
	for (int i = 1; i <= C; i ++)
		for (int j = 0; j < i; j ++)
			inv[i] = (inv[i] - 1ll * inv[j] * A[i - j] % MOD + MOD) % MOD;
}
int sum[MAXN][MAXC]= {0}, inv[MAXN][MAXC]= {0};

int ans = 0;

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	// freopen ("A.in", "r", stdin);
	// freopen ("A.out", "w", stdout);

	N = getnum (), Q = getnum ();
	for (int i = 1; i <= N; i ++) a[i] = getnum (), b[i] = getnum ();
	sum[0][0] = 1, inv[0][0] = 1;
	for (int i = 1; i <= N; i ++) mul (sum[i], sum[i - 1], i);
	inverse (sum[N], inv[N]);
	for (int i = N - 1; i >= 1; i --) mul (inv[i], inv[i + 1], i + 1);
	for (int i = 0; i <= N; i ++)
		for (int j = 1; j <= C; j ++)
			inv[i][j] = (inv[i][j] + inv[i][j - 1]) % MOD;
	for (int q = 1; q <= Q; q ++) {
		int l = getnum (), r = getnum (), V = getnum ();
		l = (l + ans) % N + 1, r = (r + ans) % N + 1;
		if (l > r) swap (l, r);
		ans = 0;
		for (int i = 0; i <= V; i ++) ans = (ans + 1ll * sum[r][i] * inv[l - 1][V - i] % MOD) % MOD;
		printf ("%d\n", ans);
	}

	return 0;
}

/*
3 3
1 1
1 2
1 3
1 3 1
1 3 2
1 3 3
*/

Problem B：博弈

题目描述

ysgh 有一棵 $n$ 个节点的树，树上在 $1$ 有一颗棋子。

ysgh 和 ysgs 利用这个棋子开始 van 游戏。具体的，ysgh 和 ysgs 轮流移动这个棋子，ysgh 先手。每次移动时，需要满足本次移动的树上距离严格大于上一次移动的树上距离（第一次移动需要满足树上距离不为 $0$），无法移动着输。他们称此游戏为 ogsc。ysgh 和 ysgs 都会做出游戏的最优决策。

ysgh 和 ysgs van 了很多游戏，渐渐觉得无聊了。

现在他们打算 van 以下游戏：

给定一颗 $n$ 个节点的树。ysgs 会选出一个包含节点 $1$ 的联通子树进行 ogsc 游戏。在两人均作最优决策的情况下，有多少个 ysgs 必胜的游戏。由于答案很大，只需要算对 $998244353$ 取膜的结果。

ysgs 花了 $0.5s$ 报出了答案，但是 ysgh 不知道是不是对的，于是他们找到了在一旁吃瓜的你。

数据范围

对 $100\%$ 的数据，$1 \le n \le 2e05, ~ T \le 10$

题解

后手必胜的条件：$1$ 位于树直径的中点上

此时若先手到达一个距离 $1$ 为 $d$ 的点上，那么后手总是可以合法地到达与先手不在同一棵 $1$ 的子树，并且距离 $1$ 也为 $d$ 的点，那么先手最终一定会被迫到达直径的一个端点，之后后手走到另一个直径的端点，那么先手就无法移动了

而若 $1$ 不在树直径的中点上，那么先手可以移动到树直径中点，而使得后手必输

现在问题转化为有多少棵连通子树满足 $1$ 位于树直径中点上

设 $f_{u, j}$ 表示以点 $u$ 为根，有多少个连通子树 $T’$ 满足 $\forall p \in T’, ~ dist (u, p) \le j$，其中 $dist (u, v)$ 表示点 $u, v$ 的树上距离

假设我们求出所有以 $1$ 为根的连通子树个数为 $tot$，那么此时只需枚举 $1$ 的每个儿子 $u$，以及 $u$ 的连通子树离 $u$ 的最大距离 $j$，强制令 $u$ 的连通子树为深度最深的，以其余 $1$ 的儿子为根的连通子树最大深度都小于它，那么这样的方案一定是不合法的，因为直径中点不可能是 $1$，统计方案数

令 $S_u$ 表示 $u$ 的儿子集合，$l_u$ 表示点 $u$ 在子树中可以到达的最远距离，公式化地，有
$$
ans = tot - \sum\limits_{u \in S_1}\sum\limits_{j = 0}^{l_u} (f_{u, j} - f_{u, j - 1}) \prod\limits_{v \in S_1 \cap u \neq v} f_{v, \min(l_v, j - 1)}
$$
那么现在问题转化为求解 $f_{u, j}$

考虑暴力，显然有
$$
\begin{aligned}
&f_{u, 0} = 2 \\
&f_{u, j} = 1 + \prod\limits_{v \in S_u} f_{v, j - 1}
\end{aligned}
$$
复杂度的症结在于 $j$ 的大小是由 $l_1$ 决定的，但实际上我们观察 $f_{v, j - 1}$ 对 $f_{u, j}$ 的贡献，只有满足 $j \le l_v$ 的才有可能被贡献到，因为 $\forall j \in (l_v, l_1], f_{v, j} = f_{v, l_v}$，看到这公式可以想到什么？长链剖分！

需要额外处理的是 $f_{v, l_v}$ 对 $f_{u, j}, j \in (l_v + 1, l_u]$，不妨用一个数组 $g$ 来储存它，即 $g_u = f_{u, l_u}$，而显然我们又不能枚举 $l_u$，这一部分的答案一开始是由重儿子继承过来的，但它们都乘上相同的 $g_v$，那么不妨用类似标记永久化的方法来记录这个 $g_v$，标记 $\forall j \in [0, l_u] f_{u, j} = f_{u, j} \times g_v$，很显然对 $j \in [0, l_v + 1]$ 还需要把 $g_v$ 除掉，因为它们不需要这个贡献

然而转移公式里还有一个 $+ 1$，那么用 $mul_u, add_u$ 分别表示标记永久化的乘和加，还需要记录一个 $imul_u$ 来记录需要除掉的 $g_v$，用 $dp_{u, j}$ 来表示没有乘上过标记的数值，它可以和 $f$ 互相转化
$$
\begin{aligned}
&f_{u, j} = dp_{u, j} \times mul_u + add_u \\
&dp_{u, j} = \frac{f_{u, j} - add_u}{mul_u}
\end{aligned}
$$
不妨用函数来表示这么一个变换，$f(u, j) = dp_{u, j} \times mul_u + add_u$ 以及 $df (u, r) = \frac{r - add_u}{mul_u}$，那么 $dp_{u, j}$ 在转移的时候就需要一直保持没累计过标记的数值，即 $dp_{u, j} = df (u, f(u, j) \times f(v, j - 1))$

但是注意，可能会存在某时刻 $f (v, l_u) \equiv 0 \pmod{998244353}$，也就是 $\forall j \in (l_v, l_u], f (u, j) = 0$，用 $lim_u$ 来记录这种 $l_v + 1$，$z_u$ 来记录在当前情况下，$0$ 所对应的未累计标记过的数值，即 $df (u, 0)$，那么对 $j < lim_u$ 则照常，对 $j \ge lim_u$ 则有 $f(u, j) = z_u \times mul_u + add_u$，其实就是直接赋值 $z_u \rightarrow dp_{u, j}$

时间复杂度 $O (T \times 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
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 998244353

using namespace std;

const int MAXN = 2e05 + 10;
const int MAXM = 2e05 + 10;

inline int power (int x, int p) {
	int cnt = 1;
	while (p) {
		if (p & 1) cnt = 1ll * cnt * x % MOD;
		x = 1ll * x * x % MOD;
		p >>= 1;
	}
	return cnt;
}
const int inv2 = power (2, MOD - 2);

struct LFS { int to, next; } ;
LFS Link[MAXM << 1];
int Head[MAXN]= {0}, size = 0;
void Insert (int u, int v) {
	Link[++ size].to = v;
	Link[size].next = Head[u];

	Head[u] = size;
}

int T, N;

int len[MAXN]= {0}, son[MAXN];
void DFS (int root, int father) {
	len[root] = 0, son[root] = - 1;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == father) continue;
		DFS (v, root);
		if (son[root] == - 1 || len[v] > len[son[root]])
			son[root] = v;
	}
	if (~ son[root]) len[root] = len[son[root]] + 1;
}
int tmp[MAXN << 1], *dp[MAXN], *id;
int mul[MAXN], imul[MAXN], add[MAXN], g[MAXN], ig[MAXN];
int lim[MAXN], zero[MAXN]= {0};
int f (int n, int k) {
	k = min (k, len[n]);
	if (lim[n] <= k) return (1ll * zero[n] * mul[n] % MOD + add[n]) % MOD;
	return (1ll * dp[n][k] * mul[n] % MOD + add[n]) % MOD;
}
int df (int n, int r) { return 1ll * (1ll * r - add[n] + MOD) % MOD * imul[n] % MOD; }
void DP (int u, int fa) {
	if (son[u] == - 1) {
		mul[u] = imul[u] = 1;
		add[u] = g[u] = 2;
		lim[u] = N + 1, ig[u] = inv2;
		return ;
	}
	dp[son[u]] = dp[u] + 1;
	DP (son[u], u);
	mul[u] = mul[son[u]], imul[u] = imul[son[u]], add[u] = add[son[u]];
	lim[u] = lim[son[u]], zero[u] = zero[son[u]];
	dp[u][0] = df (u, 1);
	for (int i = Head[u]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == fa || v == son[u]) continue;
		dp[v] = id, id += len[v] + 1, DP (v, u);
		for (int j = 1; j <= len[v] + 1; j ++) {
			if (lim[u] == j) dp[u][j] = zero[u], lim[u] ++;
			dp[u][j] = df (u, 1ll * f (u, j) * f (v, j - 1) % MOD);
		}
		if (! g[v]) { lim[u] = len[v] + 2, zero[u] = df (u, 0); continue; }
		mul[u] = 1ll * mul[u] * g[v] % MOD;
		imul[u] = 1ll * imul[u] * ig[v] % MOD;
		add[u] = 1ll * add[u] * g[v] % MOD;
		for (int j = 0; j <= len[v] + 1; j ++)
			dp[u][j] = df (u, 1ll * f (u, j) * ig[v] % MOD) % MOD;
	}
	add[u] = (1ll * add[u] + 1) % MOD;
	if (son[fa] != u) { g[u] = f (u, len[u]); ig[u] = power (g[u], MOD - 2); }
}
int gr[MAXN]= {0};
void stati (int u, int fa) {
	gr[u] = 1;
	for (int i = Head[u]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == fa) continue;
		stati (v, u);
		gr[u] = 1ll * gr[u] * (gr[v] + 1) % MOD;
	}
}
int subpro[MAXN], subflo[MAXN];
void init () {
	memset (Head, 0, sizeof (Head)), size = 0;
	memset (tmp, 0, sizeof (tmp));
	id = tmp;
	for (int i = 0; i <= N; i ++) {
		mul[i] = imul[i] = add[i] = lim[i] = zero[i] = g[i] = ig[i] = 0;
		subpro[i] = subflo[i] = 1;
	}
}
void solve () {
	DFS (1, 0); dp[1] = id, id += len[1] + 1;
	for (int i = Head[1]; i; i = Link[i].next) {
		int v = Link[i].to;
		dp[v] = id, id += len[v] + 1; DP (v, 1);
		for (int j = 0; j <= len[v]; j ++)
			subpro[j] = 1ll * subpro[j] * f (v, j) % MOD;
		if (len[v] + 1 <= len[1]) subflo[len[v] + 1] = 1ll * subflo[len[v] + 1] * f (v, len[v]) % MOD;
	}
	for (int i = 1; i <= len[1]; i ++) subflo[i] = 1ll * subflo[i - 1] * subflo[i] % MOD;
	for (int i = 0; i <= len[1]; i ++) subpro[i] = 1ll * subpro[i] * subflo[i] % MOD;
	stati (1, 0); int ans = gr[1];
	for (int i = Head[1]; i; i = Link[i].next) {
		int v = Link[i].to;
		for (int j = 0; j <= len[v]; j ++) {
			int del = (1ll * f (v, j) - (j > 0 ? f (v, j - 1) : 1) + MOD) % MOD;
			if (j > 0) del = 1ll * del * subpro[j - 1] % MOD * power (f (v, j - 1), MOD - 2) % MOD;
			ans = (1ll * ans - del + MOD) % MOD;
		}
	}
	printf ("%d\n", ans);
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	T = getnum ();
	for (int Case = 1; Case <= T; Case ++) {
		N = getnum (); init ();
		for (int i = 1; i < N; i ++) {
			int u = getnum (), v = getnum ();
			Insert (u, v), Insert (v, u);
		}
		solve ();
	}

	return 0;
}

Problem C：网络流