2.CF493E Rusty String
总结:
- fft优化字符串匹配：把字符串看作多项式 \(f(x) = \sum_{i=1}^{n}s_ix^i\) , \(s_i\) 表示字符串的第 \(i\) 位，特别的如果第 \(i\) 位是通配符那么 \(s_i = 0\). 如果第 \(i\) 位和第 \(j\) 为匹配那么 \((s_i - s_j)^2 \times s_i \times s_j\)。注意这里必须是 \((s_i - s_j)^2\) 为了保证值非负，避免抵消。那么 \(k\) 是 \(s_i\) 的周期，当且仅当 \(\forall i\leq k, (s_i - s_{n-i+1})^2 \times s_i \times s_{n-i+1}\) ，即 \(\sum_{i=1}^{k} (s_i - s_{n-i+1})^2 \times s_i \times s_{n-i+1}\) , 展开后跑多项式乘法即可。
- 如果 \(k\) 是 \(s\) 的周期，那么 \(k\) 的倍数就都是 \(s\) 的周期，如果 \(k\) 不是 \(s\) 的周期，那么一定有一个 \(k\) 的倍数不是 \(s\) 的周期。
坑:
- 认真读题，避免思维定式，这道题中的 \(?\) 不是通配符，而是任意一个字符。所以最后要根据 “总结2“，枚举 \(k\) 的所有倍数来判断 \(k\) 是不是合法周期。
CF482C Game with Strings
高维前缀和什么时候成多项式知识了？
坑:
- 如果要用 long long 类型来存一个大小大于 \(32\) 的集合，记得用
__builtin_popcountll().
CF961G Partitions
总结:
- \[ \begin{aligned} &i\binom{n - 1}{i - 1}\\ =&(i-1+1)\binom{n - 1}{i - 1}\\ =&(i-1)\binom{n - 1}{i - 1}+\binom{n - 1}{i - 1}\\ =&(n-1)\binom{n - 2}{i - 2}+\binom{n - 1}{i - 1}\\ \end{aligned} \]
-
不仅可以考虑每个数对答案的贡献，并且可以考虑每对数对答案的贡献，甚至某个数对另一个数的贡献对答案的贡献。