A There Are Two Types Of Burgers

B Square Filling

天道有轮回，$n,m$ 打反饶过谁？

C Gas Pipeline

有一段长度为 $n$ 管道，给定一个 $01$ 编码，$1$ 表示这一段管道高度为 $2$，否则可以为 $1$ 或 $2$。

$n+1$ 个端点，每个端点上设置支架，$n$ 段管道，可能在某些位置被抬高，管道单价为 $a$，支架单价为 $b$，最小化总费用。

枚举中间的每一段低处是否被完全抬起费用更低。

D Number Of Permutations

给定一个二元组的序列，求有多少种排列方式，使得两个二元组的两个维度均不单调不减。

容斥，总排列数减去分别单调和偏序单调的方案数，类似于多重集的排列。

E XOR Guessing

有一个数字 $x$，询问两次，每次询问有 $100$ 个数，返回 $x$ 和某一个询问值的异或。

第一次，询问 $1$ 到 $100$，第二次询问 $1$ 到 $100$，每个乘上 $2^7$，即第一次询问低 $7$ 位，第二次询问高 $7$ 位。

F Remainder Problem

单点更新，询问模 $x$ 余 $y$ 所有位置的和。

根号分块，模数小的，维护答案，模数大的，有贡献的位置不超过 $\sqrt{n}$。

G Indie Album

输入一个 Trie，每次询问一个输入串 $T$ 作为 Trie 上的第 $i$ 个结点的子串出现次数。

考虑都是一个串的情况，可以枚举母串的前缀在询问串 AC 自动机上的匹配结点，如果匹配点在 $fail$ 树上，到根的路径里经过询问串终点，那么当前前缀的一个后缀是询问串。

多串的情况就是在原 Trie 上 $dfs$，对询问串建 AC 自动机，维护 AC 自动机的匹配结点，单点更新，子树查询和。

$$
f_{now}=1+\sum f_{son_{now,i}} \times prime(size_{son_{now,i}})
$$

其中 $f_x$ 为以结点 $x$ 为根的子树对应的哈希值。

$size_{x}$ 表示以结点 $x$ 为根的子树大小。

$son_{x,i}$ 表示 $x$ 所有子结点之一（不用排序）。

$prime(i)$ 表示第 $i$ 个质数。

参考博客 树hash

题面

给定一棵无根树，对每个点 $i$，求 $S(u)=\sum_{i=1}^n dis(u,i)^k$，$dis(u,i)$ 表示树上路径长度。

其中 $3\le n \le 5\cdot 10^4, 1\le k \le 200$。

分析

做法一

斯特林数展开。

$$
S(u)=\sum_{i=1}^n\sum_{j=0}^k S(k,j) dis(u,i)^{\underline j}=\sum_{j=0}^k S(k,j)\sum_{i=1}^n dis(u,i)^{\underline j}
$$

其中 $n^{\underline m}=P(n,m)$ 表示 $n$ 的 $m$ 次下降幂。

记 $dp(u,i)$ 表示 $u$ 的子树下所有点对 $i$ 次下降幂的贡献，即 $\sum_{v \in subtree(u)} dis(u,v)^{\underline i}$。

转移就是考虑恒等式 $n^{\underline m}=(n-1)^{\underline m}+m\cdot n^{\underline m-1}$，做两遍 up and down 的树形 dp 即可。

做法二

$dp(u,i)$ 直接维护出 $u$ 的子树内所有点到 $u$ 的距离的 $i$ 次方之和。

转移就是考虑 $(x+y)^k$ 的二项式展开即可。