题意:

$f_{n}=\sum_{i=1}^{20} w_i*f_{n-i}$ (模一个常数)

给定$w_{1..20}$ , $f_{1..20}$ , 询问$f_n$

其中$n$以$k$进制给出,$k<=10$,$n$的位数$l<=1000$

$T$组询问,$k$都一样($T<=200$)

题解:

朴素想法是将$n$转化成$2$进制($O(l^2)$),快速幂优化矩乘($ O(l * \log_{2}{10} * 20^3 ) $)

然而这两个操作复杂度都过高，会$TLE$

考虑直接使用$k$进制，

$dp$求出所有$M^{j*k^i} ( j\in[0,k) )$

但这样$dp$复杂度为$O(l * 10 * 20^3 )$

但注意到只用$dp$一遍而不是$T$遍，所以是可以接受的。

这样单次询问复杂度就变成$ O(l * 20^3 ) $

注意到，我们要算的其实是一个$1*20$的矩阵乘多个$20*20$的矩阵

其实不用先把$20*20$的都乘起来再乘$1*20$的

可以直接依次乘

这样就只用$1*20$的乘$20*20$的

复杂度变成$ O(l * 20^2 ) $

可以通过。