当前位置：首页 > news >正文

tmp to ljh

news 2026/5/21 20:57:24

这道题是经典的 GT考试 (HNOI2008)。你的代码核心思路是正确的（KMP 自动机 + 矩阵快速幂），但在 KMP 构建、首位数字限制和初始状态赋值上存在几处致命错误。

核心问题分析

KMP 的 fail 指针构建顺序错误

问题：你在同一个 for(int i=0; i<m; i++) 循环里，同时计算当前层的 nxt、下一层的 fail，以及尝试转移到 nxt[fail[i]][szi]。
- 后果：当计算 nxt[i][szi] 遭遇不匹配时，它需要用到 fail[i] 层的 nxt。但由于你是一层层、按字符往后走的，fail[i] 的 nxt 数组在之前并没有被完全正确地扩展和保存（KMP 传统上应该用双指针或 BFS 逐层构建）。

首位数字不能为 0 的处理逻辑错误

问题：长度为 \(n\) 的数字首位不能是 0（只有 1-9）。你在 f1.a[0][0]=9, f1.a[0][1]=1; 这里试图手动初始化第一位，但这完全破坏了矩阵转移的统一性。
- 后果：如果给定的不吉利数字 s 开头本来就是 0 呢？或者开头根本不是 s[0] 和 s[1] 对应的字符呢？这样硬编码会导致第 1 步的转移逻辑与实际不符。

答案未取模

问题：最后统计 uns 总和时，你用了 uns += ans.a[0][i];。
- 后果：多个已经取模的数相加，最终结果可能大于等于 \(K\)，必须再次 % K。

正确的修改方案

最标准且不容易出错的写法是：

用标准的 KMP 递推（或者类似 AC 自动机的递推）完整求出 fail 和 nxt。
利用转移矩阵本身处理第 1 位：从特殊的初始状态（长度为 0，匹配长度为 0）出发。第 1 步转移时，限制数码只能是 1-9；后面 \(n-1\) 步转移时，数码可以是 0-9。

修改后的完整代码

#include<bits/stdc++.h>
#define ll long longusing namespace std;const int N=25; // 稍微开大一点防止越界int n,m,K;char s[25];int nxt[25][10],fail[25];
struct Matrix{ll a[N][N];
};
Matrix operator*(const Matrix &x,const Matrix &y){Matrix c;memset(c.a,0,sizeof(c.a));for(int i=0;i<m;i++){for(int j=0;j<m;j++){for(int k=0;k<m;k++){c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j])%K; }}}return c;
}
Matrix ksm(Matrix x,int ci){Matrix ans;memset(ans.a,0,sizeof(ans.a));for(int i=0;i<m;i++) ans.a[i][i]=1;while(ci){if(ci&1) ans=ans*x;x=x*x;ci>>=1;}return ans;
}
signed main()
{// 注意：读入字符串建议从下标 1 开始，更符合传统 KMP 习惯if(scanf("%d%d%d%s",&n,&m,&K,s+1) == EOF) return 0;// 1. 标准 KMP 求 fail 指针fail[1] = 0;for(int i=2; i<=m; i++){int j = fail[i-1];while(j && s[j+1] != s[i]) j = fail[j];if(s[j+1] == s[i]) j++;fail[i] = j;}// 2. 构建转移矩阵 (base) 和 第一步转移矩阵 (first_step)Matrix base, first_step;memset(base.a, 0, sizeof(base.a));memset(first_step.a, 0, sizeof(first_step.a));for(int i=0; i<m; i++){ // 当前匹配了 i 个字符for(int num=0; num<=9; num++){ // 尝试转移数字 numint j = i;while(j && s[j+1] != num+'0') j = fail[j];if(s[j+1] == num+'0') j++;// 如果新匹配长度达到了 m，说明包含了不吉利数字，丢弃该转移if(j < m){base.a[i][j]++; // 常规转移（包含0-9）if(num > 0){first_step.a[i][j]++; // 首位转移（只能是1-9）}}}}// 3. 初始状态：长度为0时，匹配不吉利数字的长度为0Matrix f1;memset(f1.a, 0, sizeof(f1.a));f1.a[0][0] = 1; // 4. 矩阵快速幂：先走首位(1-9)，再走剩下的 n-1 位(0-9)Matrix ans = f1 * first_step * ksm(base, n-1);// 5. 统计答案ll uns=0;for(int i=0;i<m;i++){uns=(uns + ans.a[0][i]) % K; // 记得每次都要取模}printf("%lld\n",uns);return 0;
}

关键改动说明

下表对齐：将 s 读入到 s+1，使字符串下标从 1 到 m，方便标准的 KMP 递推。
分离首位转移：创建了 first_step 矩阵。在构建时，只有 num > 0 才能加入到 first_step。
状态数：合法的匹配长度为 0 到 m-1，总共 m 个状态。最终统计答案时，for(int i=0;i<m;i++) 遍历所有可能的状态即可（因为达到 m 的状态压根没有记录在矩阵里）。

如果你在提交后遇到了特定的测试点报错（如编译错误或 WA），请告诉我：