vjudge 多项式

2.CF493E Rusty String

总结:

1. 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}\) , 展开后跑多项式乘法即可。
2. 如果 \(k\) 是 \(s\) 的周期，那么 \(k\) 的倍数就都是 \(s\) 的周期，如果 \(k\) 不是 \(s\) 的周期，那么一定有一个 \(k\) 的倍数不是 \(s\) 的周期。

坑:

1. 认真读题，避免思维定式，这道题中的 \(?\) 不是通配符，而是任意一个字符。所以最后要根据 “总结2“，枚举 \(k\) 的所有倍数来判断 \(k\) 是不是合法周期。

CF482C Game with Strings

高维前缀和什么时候成多项式知识了？

坑:

1. 如果要用 long long 类型来存一个大小大于 \(32\) 的集合，记得用 __builtin_popcountll() .

CF961G Partitions

总结:

1. \[ \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} \]

2. 不仅可以考虑每个数对答案的贡献，并且可以考虑每对数对答案的贡献，甚至某个数对另一个数的贡献对答案的贡献。

原文地址：http://www.cnblogs.com/i209M/p/16930598.html