例题引入

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 即可。
以上。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long
#define ri register int
#define mod 64123
int T,m,K,mxl,mx;
struct node{int n,m,a[22][22];}ans[10005],x,tmp;
int p[22];
vector<int> v[1005][10];
char s[1005];
node operator * (node as,node bs) {
    node c;c.n=as.n,c.m=bs.m;
    for(ri i=0;i<c.n;++i)
        for(ri j=0;j<c.m;++j) {
        c.a[i][j]=0;
        for(ri k=0;k<c.m;++k)
            c.a[i][j]=(c.a[i][j]+1LL*as.a[i][k]*bs.a[k][j])%mod;
    }
    return c;
}
void work() {
    for(ri i=1;i<=mxl;++i) {
        tmp.n=x.n,tmp.m=x.m;
        for(ri j=0;j<tmp.n;++j)
            for(ri k=0;k<tmp.m;++k) tmp.a[j][k]=(j==k);
        for(ri j=0;j<K;++j) {
            for(ri k=0;k<v[i][j].size();++k) ans[v[i][j][k]]=ans[v[i][j][k]]*tmp;
            tmp=tmp*x;
        }
        x=tmp;
    }
}
int main()
{
    freopen("training.in","r",stdin);
    freopen("training.out","w",stdout);
    scanf("%d%d%d",&T,&K,&m);
    for(ri i=1;i<=m;++i) scanf("%d",&p[i]),mx=max(mx,p[i]);
    x.n=mx,x.m=mx;
    for(ri i=0;i<mx-1;++i) x.a[i+1][i]=1;
    for(ri i=1;i<=m;++i) ++x.a[mx-p[i]][mx-1];
    for(ri i=1;i<=T;++i) {
        scanf("%s",s);
        int l=strlen(s);mxl=max(mxl,l);
        for(ri j=0;j<l;++j) v[l-j][s[j]-'0'].push_back(i);
        ans[i].n=1,ans[i].m=mx,ans[i].a[0][mx-1]=1;
    }
    work();
    for(ri i=1;i<=T;++i) printf("%d\n",ans[i].a[0][mx-1]);
    return 0;
}