例题引入

CLG是一个喜欢打篮球的人,他身体强壮,球技高超,成为了学校篮球队的队长。
为了锻炼腿部肌肉的力量,CLG每天都在做跳台阶的锻炼。他每次从地面(第0级台阶)开始,他会每一步往上跳若干级台阶,直到跳上n级台阶后才会休息。由于他比较奇葩,所以他每次只会跳特定的台阶数量,比如当他选择2,3,5的时候,他每一步只会往上跳2级台阶,3级台阶或者5级台阶。
一段为期为T天的跳台阶训练开始了,闲得发慌的CLG找到了你,想让你求出,如果他第i天跳正好$n_i$级台阶,有多少种不同的方案呢?两种方案不同当且仅当跳的次数不同或者某一次跳的台阶数不同。由于他非常非常的闲,所以他给你的$n_i$是一个k进制数。
你对于他这种行为表示抗议,所以你只告诉他答案对64123取模的余数。
数据范围:
T表示CLG训练的天数,k表示CLG告诉你的台阶数量的进制数,m表示CLG可能会选择的跳的台阶数,$p_i$表示CLG可能一次会跳的台阶数,$n_i$表示CLG每天训练要跳的台阶数(k进制)
$t \leq 200$,$k \leq 10$,$m \leq 20$,$p_i \leq 20$
$n_i$的位数$\leq 1000$
没错,CLG真的身体非常强壮。
时限2s。

题目分析

构建矩阵

由于数据范围太大了,所以不矩阵快速幂是行不通的。
如何构建矩阵?
我们注意到此题的状态转移应为$f(x)=\sum f(x-p_i)$,而$p_i$的数据范围非常小,所以我们可以开一个1×20的矩阵ans表示后20的答案,初始ans(0,19)=1(代表$f(0)$)
然后我们需要一个转移矩阵t。我们每次把$f(x)$所在的位置从ans(0,19)改成ans(0,18),而ans(0,19)这个位置给$f(x+1)$,因此我们的转移矩阵中$t(i+1,i)=1$(这样所有的数可以“上移”一位)
另外就是单独求出新的$f(x+1)$了,根据转移方程,我们只要让转移矩阵的$t(20-p_i,20)=1$即可。
然后我们要让答案矩阵乘以$n_i$次转移矩阵,这个可以用矩阵快速幂实现。

矩阵快速幂

我们都知道,2进制下的快速幂是这样的:
比如要求10110次幂(二进制):
这个位是从后往前算的。
第一位是0,t自乘一次。
第二位是1,ans乘一次t,t自乘一次。
第三位是1,ans乘一次t,t自乘一次。
第四位是0,t自乘一次。
第五位是1,ans乘一次t,t自乘一次。

而k进制,如十进制下的(并不快速的)幂:
要求233
第一位是3,ans乘3次t,t自乘一次。
第二位是3,ans乘3次t,t自乘一次。
第三位是2,ans乘2次t,t自乘一次。

答案求解

我们这样存答案:
开一个vector数组,v(i,j)表示第i位是数字j的询问有哪些。
然后在处理t的时候处理v(i,j)即可(详见代码里的work函数)

常数优化

首先,用struct比用class和数组都快。
然后多写几个register int
然后模数用define定义比用const int快,并且用int定义的话会出现两倍常数。
用int是比用long long快的,会爆int时强制转成long long即可。
以上。

代码