不喜欢 CTT 模拟赛。
A
我卡双模哈希？尊嘟假嘟？
考虑先构造出两个串把第一个模卡掉，然后用这两个串拼出两个串把第二个模卡掉。
两个过程是相同的。一个很唐的方法是先随机出一个串然后检查其是否有子串哈希冲突。
B
C
P2575
博弈论。可以注意到每行互不影响，所以组合游戏直接把 SG 异或起来。
然后求 SG 函数，由于一行只有 \(20\) 可以直接状压去搜。
哦对了一个状态最多 \(19\) 种后继所以 SG 函数值最大 \(19\)。
还有优先级 & > ^ > |。
此外其实做的时候感觉很像阶梯博弈但是没转化过去。
一段连续的棋子里移动相当于可以选择任意个棋子一起向后移动，很像阶梯博弈选任意石子放到下一阶。
看题解发现相当于把每个空格及其后一段连续棋子看作一个阶梯。然后就转化为阶梯博弈了。
P2290
经 PC 提点看出了 prufer 序列
PC
PC：看看这个题。
KinNa：az...prufer 序列？
PC：怎么可能，应该是 dp 吧。题解：前置知识：prufer 序列。
PC：没逝，prufer 序列 9 级，NOI 才考。
prufer 序列中每个点出现次数是其度数减一，所以这个题算一个可重集排列数就好啦。
但是怎么那么多特判点啊啊啊。
- 只有 \(1\) 个点，当且仅当度数为 \(0\) 时有一种方案。
- 存在度数为 \(0\) 的点或度数大于 \(n - 1\) 的点，无合法方案。
- \(\sum(deg_x - 1) \neq n - 2\)，无合法方案。
P2624
牢骚
你们 HNOI 这么喜欢这个 trick 吗...
\(\Huge \color{red}{计数题不取模是有什么心事吗}\)
武佬高精救我狗命
模板传三代，_____，神！
那么现在有几个不作规定的点，那么对于作规定的点可以可重集排列数算方案，在乘上一个组合数表示选了 prufer 序列里的哪些位置放这些数，剩下的位置可以随便放未作规定的点。
记点数为 \(n\)，已确定的位置个数为 \(sum = \sum_{deg_i \neq -1} (deg_i - 1)\)，未作规定的点个数为 \(cnt\)。那么答案为
\[\binom{n - 2}{sum} \frac{sum!}{\prod_{deg_i \neq -1} (deg_i - 1)!} \cdot cnt^{n - sum - 2} \]闲话
我今天那么大一节体育课呐
怎么我喜欢的游戏都在我不放假时更新，他们是约好了吗。
但是明天就是芜拉的池子了欸。
标签：题解,31,24.10,PC,序列,prufer,sum,deg From： https://www.cnblogs.com/KinNa-Sky/p/18518937感觉我接触到的 OI 圈子舟含量很高？