GT考试 [矩乘系列]

· · 个人记录

前言：

应某人的要求，写一下题解。

这题折磨吗，不折磨，折磨吗，不折磨。所以宇宙万法的源头是什么？如如，所以折磨吗，如折。

题目传送门

解题思路：

首先，容易想到递推 n （矩乘不递推大的推什么？），枚举当前合法方案中的后缀再多出一个字符后是否会变的不合法。看到 m 的范围，尝试dp。

设 f_{i,j} 表示当前为第 i 位，有长度为 j 的不吉利数字的后缀的方案数， g_{i,j} 表示后缀长度为 i 的不吉利数字加上一个字符后变为后缀长度为 j 不吉利数字的方案数。我们就可以推出：

f_{i,j}= \sum_{k=0} ^{m}f_{i-1,k} \times g_{k,j}

这里的 g_{k,j} 根据定义显然是可以预处理的。但是我的评价是：暴力处理甚至都没有KMP好想。前缀匹配后缀那可不就是KMP吗！所以直接上KMP。

再接下来就是构造矩阵了。首先， m 的长度很小，所以可以构造一个 m \times m 大小的矩阵：

\begin{bmatrix} f_{i,0}\\f_{i,1}\\ \vdots \\f_{i,m-1}\end{bmatrix}

初态就是 f_{0,0}=1 （空串），对应到矩阵上就是：

\begin{bmatrix}\,1 \,\\ \,0 \, \\ \, 0 \, \\ \, \vdots \, \\\,0 \, \end{bmatrix}

最重要的就是如何构造操作矩阵了。因为是 f_{i-1,k} \times g_{k,j} \to f_{i,j} 的，所以是由第 k 个转移到第 j 个，也就是第 k 行和第 j 列。所以操作矩阵异常的简单，就是：

\begin{bmatrix}g_{0,0},g_{0,1},\cdots ,g_{0,m-1}\\g_{1,0},g_{1,1},\cdots ,g_{1,m-1}\\ \vdots \\ g_{m-1,0},g_{m-1,1}, \cdots ,g_{m-1,m-1} \end{bmatrix}

上述即为：

\begin{bmatrix} f_{i+1,0}\\f_{i+1,1}\\ \vdots \\f_{i+1,m-1}\end{bmatrix} = \begin{bmatrix}g_{0,0},g_{0,1},\cdots ,g_{0,m-1}\\g_{1,0},g_{1,1},\cdots ,g_{1,m-1}\\ \vdots \\ g_{m-1,0},g_{m-1,1}, \cdots ,g_{m-1,m-1} \end{bmatrix} \times \begin{bmatrix} f_{i,0}\\f_{i,1}\\ \vdots \\f_{i,m-1}\end{bmatrix}

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
    x=0;int f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    x*=f;
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){if(x<0){putchar('-'),x=-x;}if(x>9)write(x/10);putchar(48+x%10);}
TP void writeln(T x){if(x<0){putchar('-'),x=-x;}if(x>9)write(x/10);putchar(48+x%10);puts("");}
TP_ void writeln(const T x,T_ ...y){write(x);putchar(' ');writeln(y...);}
typedef long long LL;
int n,m,P;
char s[25];
int p[25];
int match[25][25];
struct matrix
{
    LL a[25][25];
    matrix()
    {
        memset(a,0,sizeof(a));
    }
    friend matrix operator *(const matrix &A,const matrix &B)
    {
        matrix C;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=m;j++)
                for(int k=1;k<=m;k++)
                    C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j]%P)%P;
        return C;
    }
}F,f;
matrix qpow(matrix a,LL b)
{
    matrix ans;for(int i=1;i<=m;i++)ans.a[i][i]=1;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a;
        a=a*a;
    }
    return ans;
}
void KMP()
{
    int len=strlen(s+1);
    p[1]=0;
    for(int i=2,j=0;i<=len;i++) 
    {
        while(j&&s[i]!=s[j+1])j=p[j];
        if(s[i]==s[j+1])j++;
        p[i]=j;
    }
    for(int i=0;i<m;i++) 
    {
        for(int j='0';j<='9';j++) 
        {
            int temp=i;
            while(s[temp+1]!=j&&temp)temp=p[temp]; 
            if(s[temp+1]==j)temp++; 
            match[i+1][temp+1]++; 
        }
    }
}
int main()
{
    read(n,m,P);
    scanf("%s",s+1);
    KMP();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            f.a[i][j]=match[i][j];
    F.a[1][1]=1;
    LL ans=0;
    F=F*qpow(f,n);
    for(int i=1;i<=m;i++)
        ans=(ans+F.a[1][i])%P;
    writeln(ans);
    return 0;
}