题解 杂题 算法

Acwing P1035 (HNOI2008) GT考试

---

题目链接：点我

题目大意

给定一个长度为$M$的由数字组成的字符串$S$，要求构造一个长度为$N$的由数字构成的字符串$T$，使得$T$中不包含$S$。
输出方案数$mod \ K$的值。

输入$N,M,K$和字符串$S$。

样例输入

4 3 100
111

样例输出

81

数据范围

• $1 \leq N \leq 10^9$
• $1 \leq M \leq 20$
• $2 \leq K \leq 1000$

---

解析

做这道题前，我们可以先看一下前置题这里。

两道题唯一不同的地方就是，这道题$N$的范围扩大到了$10^9$,比原先大了不少。

我们可以先看看$N=30$时的思路：

• 这道题肯定是一道DP，具体参见Acwing上的状态机DP。
• 我们设$f[i][j]$表示长度为$i$，且不包含$S$串，且串尾与$S$匹配的最大长度为$j$的所有方案。
• 对于当前的字符串，我们需要在其后添加一个新数。如果添加了之后，所成的后缀子串仍能够与$S$匹配，那么j+1;否则应重新匹配最大长度。

• 于是，我们便得到了状态转移方程：
  

  $$f[i+1][k]+=f[i][j]$$

• 对于字符串快速匹配，我们又要请出这位大神——$kmp$算法。它可以快速求出一个数组$ne[i]$，表示一个字符串的前$i$位中的最大前后缀匹配，具体原理不作讲解。如，对于字符串$abcdabcef$，则$ne[7]=3$。

这里给出代码：

#include<bits/stdc++.h>
using namespace std;
const int N=55,mod=1e9+7;
int n,m;
char str[N];
int ne[N];
int f[N][N];
int main()
{
    cin>>n;
    cin>> str+1;
    m=strlen(str+1);
    for(int i=2,j=0;i<=m;i++){
        while(j&&str[j+1]!=str[i]) j=ne[j];
        if(str[j+1]==str[i]) j++;
        ne[i]=j;
    } //kmp
    f[0][0]=1;
    for(int i=0;i<n;i++)//枚举每个点
        for(int j=0;j<m;j++)//枚举最大后缀匹配长度
            for(int c='a';c<='z';c++){//枚举要添加的字符
                int k=j; 
                while(k&&str[k+1]!=c) k=ne[k]; //如果添加后不匹配，则重新找到最大的匹配长度
                if(str[k+1]==c) k++;
                if(k<m) f[i+1][k]=(f[i+1][k]+f[i][j])%mod;
                //这里k必须小于m，表示组成的新字符串中不能包含长度为m的字符串S
            }
    int ans=0;
    for(int i=0;i<m;i++) ans=(ans+f[n][i])%mod; //统计答案
    cout<<ans;
}

然后我们回头来看这道题。

对于$N \leq 10^9$，再枚举每个点肯定不现实。

于是，我们考虑一个两层状态之间的一个转换，即$f[i]与f[i+1]$之间的转换：

$$f[i+1][0]=a_{00}*f[i][0]+a_{01}*a[i][1]+……$$
$$f[i+1][1]=a_{10}*f[i][0]+a_{11}*a[i][1]+……$$
$$……$$

其中$a_{jk}$表示对于上述代码的25行要执行的次数。

然后不难发现，所有的$a_{jk}$可以组成一个矩阵$A$。于是，转移方程就发生了变化：

$$f[i+1]=f[i]*A$$
所以答案$f[n]=f[0]*A^n$。
矩阵乘法可以轻松解决。

对于矩阵$A$，在上面代码的状态转移部分，我们可以预处理出。(具体见代码，还可以自己画图分析分析)。

---

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,m,mod;
char str[N];
int ne[N];
int a[N][N];
inline void mul(int c[N][N],int a[N][N],int b[N][N]){
    static int t[N][N];
    memset(t,0,sizeof t);
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<m;k++)
                t[i][j]=(t[i][j]+a[i][k]*b[k][j])%mod;
    memcpy(c,t,sizeof t);
}//矩阵乘法模板
int qpow(int k){
    int f[N][N]={1}; //这里写二维数组只是为了方便计算。实际上在计算时，f数组中只有f[0]这一数组在使用，其他都没有用处。
    while(k){
        if(k&1) mul(f,f,a);
        mul(a,a,a);
        k>>=1;
    }
    int res=0;
    for(int i=0;i<m;i++)res=(res+f[0][i])%mod; //计算答案
    return res;
}
int main()
{
    cin>>n>>m>>mod;
    cin>> str+1;
    for(int i=2,j=0;i<=m;i++){
        while(j&&str[j+1]!=str[i]) j=ne[j];
        if(str[j+1]==str[i]) j++;
        ne[i]=j;
    } //kmp
    for(int j=0;j<m;j++)
        for(int c='0';c<='9';c++){
            int k=j;
            while(k&&str[k+1]!=c) k=ne[k];
            if(str[k+1]==c) k++;
            if(k<m)a[j][k]++; //将上面代码中状态转移部分改为预处理，可求出矩阵A
        }
    cout<<qpow(n); //矩阵快速幂
    return 0;
}

完结撒花~