题意:
$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 ) $
可以通过。