G
一个圆周的 m m m等分点编号分别为 1 ∼ n 1\sim n 1∼n， n n n只蟋蟀分别在编号 A 1 , A 2 , . . . , A n A_1,A_2,...,A_n A1,A2,...,An的点上。每秒，第 i i i只蟋蟀跳到 A i A_i Ai关于 A i + 1 A_{i+1} Ai+1对称的点上。求 t t t秒后每个蟋蟀的位置。
首先，把编号 n n n改成 0 0 0。
即求 [ x k + t ] ( 2 − x ) t ∑ i = 0 n − 1 A i x i 1 − x n ( 0 ≤ k ≤ n − 1 ) [x^{k+t}] \frac{(2-x)^t\sum_{i=0}^{n-1}A_ix^i}{1-x^n}(0\le k\le n-1) [xk+t]1−xn(2−x)t∑i=0n−1Aixi(0≤k≤n−1)
即对 ( 2 − x ) t ∑ i = 0 n − 1 A i x i (2-x)^t\sum_{i=0}^{n-1}A_ix^i (2−x)t∑i=0n−1Aixi进行长度为 n n n的循环卷积。
可以通过快速幂求出 ( 2 − x ) t (2-x)^t (2−x)t，每一步都把长度压到 n n n。然后再和 ∑ i = 0 n − 1 A i x i \sum_{i=0}^{n-1}A_ix^i ∑i=0n−1Aixi卷积一下。
另外，可以用Bluestein算法:
一般地，设 F ( x ) = ∑ i = 0 n − 1 a i x i F(x)=\sum_{i=0}^{n-1}a_ix^i F(x)=∑i=0n−1aixi
F ( ω n k ) = ∑ i = 0 n − 1 a i ω n k i = ∑ i = 0 n − 1 a i ω n ( k + i 2 ) − ( k 2 ) − ( i 2 ) = ω n − ( k 2 ) ∑ i = 0 n − 1 a i ω n − ( i 2 ) ω n ( i + k 2 ) F(\omega_n^k)=\sum_{i=0}^{n-1}a_i\omega_n^{ki}=\sum_{i=0}^{n-1}a_i\omega_n^{\binom{k+i}{2}-\binom{k}{2}-\binom{i}{2}}=\omega_n^{-\binom{k}{2}}\sum_{i=0}^{n-1}a_i\omega_n^{-\binom{i}{2}}\omega_n^{\binom{i+k}{2}} F(ωnk)=i=0∑n−1aiωnki=i=0∑n−1aiωn(2k+i)−(2k)−(2i)=ωn−(2k)i=0∑n−1aiωn−(2i)ωn(2i+k)
令 f i = a i ω n − ( i 2 ) , g i = ω n ( 2 n − i 2 ) f_i=a_i\omega_n^{-\binom{i}{2}},g_i=\omega_n^{\binom{2n-i}{2}} fi=aiωn−(2i),gi=ωn(22n−i)
F ( ω n k ) = ω n − ( k 2 ) ∑ i = 0 n − 1 f i g 2 n − k − i = ω n − ( k 2 ) ( f g ) 2 n − k F(\omega_n^k)=\omega_n^{-\binom{k}{2}}\sum_{i=0}^{n-1}f_ig_{2n-k-i}=\omega_n^{-\binom{k}{2}}(fg)_{2n-k} F(ωnk)=ωn−(2k)∑i=0n−1fig2n−k−i=ωn−(2k)(fg)2n−k
这样DFT后直接对点值运算即可。
H
一棵树，从 s s s点出发，在 m m m点可获得地图，问至少多少次可确保到达终点。
以 m m m点为根，可以发现，经过任意一个点，都只有直接去 m m m点和先遍历完子树再去 m m m点两种选择。
因此可以树形DP。
K
允许有一位不同的字符串匹配，有多个模式串。（总长度 1.2 e 6 1.2e6 1.2e6）
若必须全部匹配，可以跑AC自动机。
允许不同时，用扩展KMP求出待匹配串各个位置和模式串的最长公共前缀、后缀长度。
京公网安备 11010502036488号