Jagiellonian U Contest补题

    科技2024-11-09  13

    G

    一个圆周的 m m m等分点编号分别为 1 ∼ n 1\sim n 1n 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]1xn(2x)ti=0n1Aixi(0kn1) 即对 ( 2 − x ) t ∑ i = 0 n − 1 A i x i (2-x)^t\sum_{i=0}^{n-1}A_ix^i (2x)ti=0n1Aixi进行长度为 n n n的循环卷积。 可以通过快速幂求出 ( 2 − x ) t (2-x)^t (2x)t,每一步都把长度压到 n n n。然后再和 ∑ i = 0 n − 1 A i x i \sum_{i=0}^{n-1}A_ix^i i=0n1Aixi卷积一下。

    另外,可以用Bluestein算法: 一般地,设 F ( x ) = ∑ i = 0 n − 1 a i x i F(x)=\sum_{i=0}^{n-1}a_ix^i F(x)=i=0n1aixi 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=0n1aiωnki=i=0n1aiωn(2k+i)(2k)(2i)=ωn(2k)i=0n1aiω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(22ni) 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=0n1fig2nki=ωn(2k)(fg)2nk 这样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求出待匹配串各个位置和模式串的最长公共前缀、后缀长度。

    Processed: 0.022, SQL: 8