标签 MTT 下的文章

先看 n=1 的情况,考虑令 a = w_{1, 1} ,用 f_i 表示跳了 i 步的答案,则 f_i = a^i \binom n i

考虑

\begin{aligned} ans &= \sum_{i \bmod k=m} f_i = \sum_{i \bmod k=m} a^i \binom ni \\ &= \sum_{i=0}^n [k|i-m] a^i \binom ni \\ &= \sum_{i=0}^n \frac 1k \sum_{j=0}^{k-1} \omega_k^{j(i-m)} a^i \binom ni \\ &= \frac 1k \sum_{j=0}^{k-1} \omega^{-mj}_k \sum_{i=0}^n \binom ni (\omega^{j}_k a)^i 1^{n-i} \\ &= \frac 1k \sum_{i=0}^{k-1} \omega^{-mi}_k \left(\omega^i_k a + 1\right)^n \end{aligned}

考虑后面的 \displaystyle{\left(\omega^i_k a + 1\right)^n} 对于固定的 i 是相同的,可以与先处理出 i \in [0, k) 的值,设为 c(i)

前面的部分有个暴力的做法就是多项式多点求值出多项式 \displaystyle{\frac 1k \sum_{i=0}^{k-1} x^i c(i)}\omega_k^0, \omega_k^{-1}, \omega_k^{-2} ... \omega_k^{-k+1} 的值,复杂度 O(k \log^2 k),然而貌似被针对了过不去 ...

考虑一个优秀一点的做法,如何处理 \omega^{-mj}?毛爷爷论文中有个做法是把 ij 拆成 \frac {(i+j)^2} 2 - \frac {i^2} 2 - \frac {j^2} 2 ,然而此题中可能存在单位根没有二次剩余的情况。考虑把 ij 拆成 \binom {i+j} 2 - \binom i2 - \binom j2 ,那么原式可以化为

\begin{aligned} ans &= \frac 1k \sum_{i=0}^{k-1} \omega^{-mi}_k c(i) \\ &= \frac 1k \sum_{i=0}^{k-1} \omega^{\binom {i-m} 2 - \binom i2 - \binom {-m}2} _k c(i) \\ &= \frac {\omega^{- \binom {-m}2}} k \sum_{i=0}^{k-1} \omega^{\binom {i-m} 2}_k \left( \omega^{- \binom i2}_k c(i)\right) \\ \end{aligned}

显然是一个卷积的形式,那么卷积下即可,复杂度 O(k \log k)

考虑 n \le 3 的情况,原来的转移会变成矩阵,感兴趣的读者可以先做下 BZOJ3328 PYXFIB ,与 n = 1 是本质相同的,并且可以发现 c(i) 仍然是一个常数,同理处理下再卷积即可。

READ MORE