题目大意

考虑现在有$n \times (L+1)$个点，每个点用一个坐标$(x,y)$表示。（$x \in [0,L],y \in [1,n]$）

一开始我们在$(0,x)$处，接下来每次可以跳若干步，从$(a,x)$跳到$(b,y)$（$a < b$）的方案数为$w[a][b]$，求在跳了$x$次后到达$(L,y)$的方案数，$x$满足$x \bmod d=k$，对于$k\in[0,t-1]$都输出一个答案。

给定$n,w[][],L,x,y,d,t$，答案对质数$P$取模，保证有在模$P$意义下的$d$次单位根。

题解

考虑若对$x$的限制是$x=L$，那么这个问题可以直接使用矩阵快速幂解决。

加上题目里都明示要用单位根反演了，那我们考虑用单位根反演来解决这个问题。

我们可以比较容易地想到这个多项式：

$f(x)=\left( \begin{bmatrix} 1 \ 0 \ 0 \\ 0 \ 1 \ 0 \\ 0 \ 0 \ 1 \end {bmatrix} + Wx \right)^L$

其中，$W$是一个矩阵，数值就是给定的w数组。

那么我们要求的东西就是这个：

$Ans_k=\sum_{i=0}^L [x \bmod k=t] [x^i]f(x) \qquad (for \ k \in[0,t-1])$

然后就可以用矩阵乘法求答案了！

我们考虑使用单位根反演。注意：为了处理不是$d$的整次幂的情况，我们可以直接乘上一个$x^{d-k}$。

$\begin{aligned} Ans_k &= \frac{1}{d} \sum_{i=0} ^{d-1} f(\omega_{d}^{i})(\omega_d^{i})^{d-k} \\ Ans_k &= \frac{1}{d} \sum_{i=0} ^{d-1} \omega_d^{-i\times k} \times f(\omega_{d}^{i}) \end{aligned}$

注意到：$i \times k= {i +k \choose 2} - {i \choose 2} - {k \choose 2}$。

代入可得

$\begin{aligned} Ans_k = \frac{1}{d} \sum_{i=0} ^{d-1} \omega_d^{ {k \choose 2} + {i \choose 2} - {i+k \choose 2} } \times f(\omega_{d}^{i}) \\ Ans_k = \frac{\omega_d^{ {k \choose 2} } }{d} \sum_{i=0} ^{d-1} \omega_d^{-{i+k \choose 2} } \times ( f(\omega_{d}^{i}) \times \omega_d^{ {i \choose 2} } ) \end{aligned}$

后面的用矩阵快速幂预处理。

差一定的卷积，请。

（要写任意模数卷积。）

代码请移步Github仓库。