CF1334 E
结论是一定是 \(x -> gcd(x, y) ->y\) 这样子的走法。
所以直接对 \(D\) 所有因子预处理即可。
Loj3093 BJOI2019 光线
设 \(P\) 表示透光率， \(Q\) 表示反射率， 转移即可。
[CQOI2018]破解D-H协议
直接 \(bsgs\) 板子 ？
SDOI2018反回文串
牛逼， 给跪了。
P2606 [ZJOI2010]排列计数
你们放这样的题目在题单里面显得我很憨。
P4461 [CQOI2018]九连环
直接 python 不和你多BB。
[JXOI2018]游戏
简单题， 考虑那些必须被访问的数即可。
然后根据期望 \(k\) 大值的那个结论直接计算位置的期望即可。
\(\frac{k}{k + 1} \times MAXVALUE\)
P5339 [TJOI2019]唱、跳、rap和篮球
鲲鲲题， 很好。
题意就是有 \(a\) 个喜欢唱的， \(b\) 个喜欢跳的， \(c\) 个喜欢rap的， \(d\) 个喜欢篮球的， 让你选 \(n\) 个排成一排， 使得没有人谈论鸡你太美。
讨论鸡你太美指连续四个人分别喜欢唱跳rap篮球。
\(n \leq 1000, a, b, c, d\leq 500\)
这种东西一看就容斥， 而且和二项式反演脱不了关系。
设 \(f(k)\) 表示至少有 \(k\) 组人讨论鸡你太美， \(g(k)\) 表示恰好有 \(k\) 组人讨论鸡你太美。
那个 \(\binom{n - 3k}{k}\) 就是把 \(4\) 个人看成一个， 然后选 \(k\) 个展开。
后面的 \(S\) 就是在 \(a - k, b - k, c - k, d - k\) 条件下， 选出来 \(n - 4k\) 个组成序列的方案数。
直接 \(NTT\) 即可。
注意 \(O2\) 并不会优化模数不加 const 的情况。
CF750G New Year and Binary Tree Paths
P5342 [TJOI2019]甲苯先生的线段树
和上面那个一样。
CZT
P5293 [HNOI2019]白兔之舞
白兔之舞就这啊
单位根反演+MTT卷就完了， 没啥思维难度。
科技难度另说
Luogu4007 小 Y 和恐怖的奴隶主
设 \(f(i, a, b, c, d)\) 表示进行了前 \(i\) 次攻击以后， 当前有 \(a\) 个剩下一滴血的， \(b\) 个剩下两滴的， \(c\) 个剩下一滴的。
那么答案就是 \(\sum_{i = 0}^{n - 1} f(i, a, b, c, d) \times \frac{1}{a + b + c + 1}\) 。
观察到状态数必定不多， 可以设一个 \(g\) 表示当前答案的计数， 和 \(f\) 一起矩乘即可。
[ZJOI2020] 传统艺能
线段树恐惧症好吧。
题意就是给你一个广义的线段树， 然后随便选一个区间打标记， 问最后有标记的点的期望个数。
做法是考虑每个点贡献到答案里面的概率， 现在考虑怎么算这个概率。
一个点被打标记肯定有三个状态， 自己本身有标记， 祖先有标记被推下来，自己和祖先都没有标记。
不妨设当前点为 \(i\), 操作了 \(j\) 次后自己有标记的概率是 \(f_j\), 祖先有标记的概率是 \(g_j\)， 自己和祖先都没有标记的概率是 \(h_j\) 。
然后再考虑转移的概率。
考虑求一个 \(a_i\) 表示一次的操作区间完全包含了 \(i\) 的概率， \(b_i\) 表示一次区间操作可以把祖先节点的标记下传到 \(i\) 的概率， \(c_i\) 表示一次操作区间和 \(i\) 不交的概率，\(d_i\)表示递归到 \(i\)并打标记， \(e_i\) 表示递归到儿子归到 \(i\) 的概率。
不妨设 \(S\) 表示 \(n(n + 1)\times 2\), \(L, R\) 表示当前节点的管辖区间。
然后考虑转移，
\(f\) 是考虑不能递归到儿子来转移。
\(g\) 是考虑不能把祖先的标记放下来。
\(h\) 考虑放标记， 放祖先标记， 打不到标记。
矩乘即可。