「比赛总结」正睿省选失恋测
正睿十连测 Round 8 补题记录。 菜到去世……
陈太阳的石子游戏
有 \(n\) 堆石子，每堆石子被染成了黑色或者白色，第 \(i\) 堆石子有 \(a_i\) 个石子。陈太阳和杨主力轮流操作，杨主力先操作。操作有两种，他们每次可以选择一种进行操作：
- 从石子数量最少的黑堆中取出任意正整数数量的石头
- 从任何白堆中取出任意正整数数量的石头
不能操作的玩家将会输掉游戏。现在所有石头堆都是固定的，但尚未着色。 陈太阳贿赂了裁判，使他有机会自己给所有石头涂色。 现在，他想知道有多少种涂色方法使得自己能赢下游戏？ 由于答案可能太大，因此只需要输出模 \(1 000 000 007\) 答案即可。
\(n\le 10^6\)
好吧 - -这才明白什么叫做 SG 函数。
Sprague-Grundy(SG)定理
对于一个完整的游戏局面 \(G\) ，有若干个子游戏 \(G_0, G_1, G_2, \cdots\) 那么： \[ \operatorname{SG}(G) = \bigoplus\limits{G_i} \] 对于一个局面 \(x\) ，若其有若干个后继局面，则： \[ \operatorname{SG}(x) = \operatorname{mex}\{ \operatorname{SG}(y) \mid y \text{是} x \text{后继} \} \] 特殊地，若一个局面 \(P\) 没有后继局面，则其 \(\operatorname{SG}\) 值为 \(0\)。
首先考虑必胜局面条件是什么：
对一个局面划分子游戏，显然，白色石头和黑色石头可以作为两个子游戏，白色石头构成一个经典的 Nim 游戏。只需要考虑黑色石头的 \(\operatorname{SG}\) 值即可。
通过手算不难发现黑色石头的 \(\operatorname{SG}\) 值为： \[ \text{最小堆中的石头数}-(\text{最小堆的数量}+[\text{所有黑色石头堆都具有相同的大小}]) \% 2 \] 先按照石子数量排序。
可以考虑枚举最小堆出现次数和石子数量 \(x\)，石子数量小于 \(x\) 的石子堆一定是白色堆，枚举一个出现次数，可以算出石子数量等于 \(x\) 和小于 \(x\) 的堆的 \(\operatorname{SG}\) 值 \(z\)，然后考虑后面的石子堆有多少种选法，使得其 \(\operatorname{SG}\) 值等于 \(z\) 即可。这个问题是 线性基 的经典问题。
陈阳太的集合
陈阳太有个集合 \(U=\{ 1,2,3,⋯,n \}\) 她打算和杨主力轮流操作。
- 陈阳太负责一次拆分操作。具体地，陈阳太会将集合 \(U\) 分成至少两个非空集合，它们的并集为 \(U\) 且两两交集均为 \(\varnothing\)。
- 杨主力负责多次合并操作。具体地，杨主力首先收到陈阳太操作后的所有集合，随后每当杨主力手上存有多于一个集合，则必须取出两个集合合二为一，即取出的集合消失并获得它们的并集。
显然最终杨主力将获得集合 \(U\)，同时操作结束。
定义两局操作不同，当且仅当存在集合 \(S\)，在一局操作中出现过且在另一局操作中从未出现。注意，与操作次序无关。
求杨主力和陈阳太一共有多少局不同的操作，对 NTT 质数取模。
\(n \le 10^6\)
只考虑如何合并一些集合，可以倒过来考虑，考虑一开始有一个全集 \(U\) ，如何拆分成若干个子集，显然每一种拆分方式对应一个操作等价类。
考虑递推式：
设 \(f(n)\) 为将元素个数为 \(n\) 的集合拆分成若干个集合的情况。
易知递推式为： \[ f(n) = 1 + \frac{1}{2}\sum_{i=1}^{n-1}\dbinom{n}{i}f(i)f(n - i) \] 其中 \(+1\) 是考虑到这个集合就在这里停止划分，后面的 \(\frac{1}{2}\) 是因为划分没有什么顺序性。
可以考虑生成函数优化，这个式子后面的项稍微补补就是一个卷积，先定义 \(f(0)=1\)，可以把式子写成： \[ f(n) = 1 + \frac{1}{2}\left[\left(\sum_{i=0}^{n}\dbinom{n}{i}f(i)(n-i)\right) - 2 \times f(n)\right] \]
\[ 2f(n) = 1 + \frac{1}{2}\sum_{i=0}^{n}\dbinom{n}{i}f(i)(n-i) \]
补齐常数项： \[ 2f(n) = 1 + \frac{[n=0]}{2} + \frac{1}{2}\sum_{i=0}^{n}\dbinom{n}{i}f(i)(n-i) \] 有组合数，考虑指数生成函数： \[ 2\frac{f(n)}{n!} = \frac{1 + \frac{[n=0]}{2}}{n!} + \frac{1}{2}\sum_{i=0}^{n}\frac{f(i)}{i!}\frac{f(n-i)}{(n-i)!} \] 设 \(F(x) = \sum_{i \ge 0} f(i)\frac{x^i}{i!}\) \[ 2F(x)=e^x+\frac{1}{2}+\frac{1}{2}F^2(x) \] 解出 \(F(x)\) 根据常数项，得到最终取值为： \[ F(x) = 2 + \sqrt{3+2e^x} \] 需要一个多项式开方。大佬们对长度为 \(10^6\) 的多项式开方都冲到 \(500ms\) 了，我的甚至需要跑 \(8s\) 左右，就很震撼 /kk。
题目关键是对计数对象的转化，需要根据题目描述的等价类划分方式，确定转化为何种计数对象。
陈太阳的树
陈太阳有一棵 \(n\) 个点的树，每条边 \(e_i\) 上有一个非空字母集合 \(S_i \subset \{'a','b',\cdots,'z'\}\)，陈太阳还有一个模板串集合 \(T = \{t_1, t_2, \cdots, t_m\}\)
杨主力给了陈太阳 \(q\) 次询问，每次询问给定一条从 \(u\) 到 \(v\) 的有向树链，问有多少种在树边上选字母的方案，使得将所有树链上的字母按照从 \(u\) 到 \(v\) 的顺序写出来之后形成的字符串包含模板串集合中至少一个模板串。
杨主力不想让答案数字太大，于是陈太阳只需要告诉杨主力对 998244353 取模的结果就好了。
输入第一行两个正整数 \(n,m,q\)，分别表示树的大小，模板串集合的大小以及询问的个数。
接下来 \(n-1\) 行，每行两个正整数 \(u,v(1 \le u < v \le n)\) 以及一个字符串 \(s\)，表示 \(u\) 点到 \(v\) 点之间有一条边，边上的非空字母集合由 \(s\) 中的所有字母构成。保证 \(s\) 只包含小写字母且不包含重复的字符
接下来 \(m\) 行，每行一个字符串，表示一个模板串。保证所有模板串的长度之和不超过 40
接下来 \(q\) 行，每行两个正整数 \(u,v(1 \le u,v \le n, u\neq v)\)，表示一次询问。
\(1\le n \le 2500, 1\le q \le 5000, 1\le m \le 40, \sum|t_i|\le 40\)
多模板匹配问题，显然需要 AC 自动机，显然可以在 AC 自动机上对路径 dp。
一个 AC 自动机的技巧：如果只是想判断 AC 自动机中是否存在一个模板串可以在文本串中完全匹配，可以考虑强制将 AC 自动机中每一个模板串结束字符对应结点的出边全都连向自己。最后走完文本串后一定会停留在一个模板串结尾的对应结点。
但是这里的文本串不确定，就可以考虑在 AC 自动机上 dp。
设 \(dp[n][u]\) 表示考虑了路径的前 \(n\) 个结点，到达结点 \(u\) 的路径个数。
如果每次暴力 dp 就能够得到 \(\mathcal{O}(qnt^3)\) 的做法。
考虑到每个边的转移其实是相似的，按照动态 dp 的套路可以把每一条树边的贡献理解为一种线性变换？考虑使用矩阵乘法表示转移，每一条树边就对应一个矩阵，可以倍增预处理就能够做到单次询问 \(\mathcal{O}(t^2\log n)\) 的复杂度。
可以考虑树剖然后线段树维护矩阵乘积。
还可以点分之后预处理每个点到其祖先路径上的矩阵乘积，然后点分树上合并矩阵乘法。
还可以点分之后离线处理每个询问。
能过几个就不得而知了