题目链接：
显而易见的动态规划加矩阵快速幂，不过转移方程不怎么好想，dp[i][j]表示长度为i的准考证号后j位与不吉利数字的前j位相同的方案数。则：
转移方程为$dp[i][j]=\sum_{k=0}^{m-1}dp[i-1][k]*g[k][j]$
答案为：$ans=\sum_{i=0}^{m}dp[n][i]$
g[i][j]表示长度为i的后缀变成长度为j的后缀的方案数。
而g数组可以用kmp预处理出来
附上洛谷40分不用矩阵优化的代码
1 1 #include2 2 using namespace std; 3 3 typedef long long ll; 4 4 typedef unsigned long long ull; 5 5 const int maxn = 6e6 + 10; 6 6 ll Next[25]; 7 7 ll g[25][25]; 8 8 ll dp[maxn][25]; 9 9 char s[25];10 10 void getN(int n) {11 11 Next[0] = -1;12 12 int i = 0, j = -1;13 13 while (i < n) {14 14 if (j == -1 || s[i] == s[j])15 15 Next[++i] = ++j;16 16 else17 17 j = Next[j];18 18 }19 19 }20 20 int main() {21 21 ll n, m, mod;22 22 scanf("%lld%lld%lld", &n, &m, &mod);23 23 scanf("%s", s);24 24 getN(m);25 25 Next[0] = 0;26 26 for (int i = 0; i < m; i++) {27 27 for (int j = '0'; j <= '9'; j++) {28 28 int t = i;29 29 while (t&& s[t] != j)30 30 t = Next[t];31 31 if (s[t] == j)32 32 t++;33 33 g[i][t]++;34 34 }35 35 }36 36 dp[0][0] = 1;37 37 for (int i = 1; i <= n; i++) {38 38 for (int j = 0; j < m; j++) {39 39 for (int k = 0; k < m; k++) {40 40 dp[i][j] = (dp[i][j] + dp[i - 1][k] * g[k][j]) % mod;41 41 }42 42 }43 43 }44 44 ll ans = 0;45 45 for (int i = 0; i < m; i++)46 46 ans = (ans + dp[n][i]) % mod;47 47 printf("%lld\n", ans);48 48 }
以及正解
1 #include2 using namespace std; 3 typedef long long ll; 4 typedef unsigned long long ull; 5 const int maxn = 6e6 + 10; 6 ll Next[25]; 7 ll n, m, mod; 8 ll dp[25][25]; 9 char s[25];10 void getN(int n) {11 Next[0] = -1;12 int i = 0, j = -1;13 while (i < n) {14 if (j == -1 || s[i] == s[j])15 Next[++i] = ++j;16 else17 j = Next[j];18 }19 }20 struct matrix {21 ll cnt[25][25];22 matrix() { memset(cnt, 0, sizeof(cnt)); }23 matrix operator *(const matrix a)const {24 matrix ans;25 for (int i = 0; i <= m; i++) {26 for (int j = 0; j <= m; j++) {27 ans.cnt[i][j] = 0;28 for (int k = 0; k <= m; k++)29 ans.cnt[i][j] = (ans.cnt[i][j] + cnt[i][k] * a.cnt[k][j]) % mod;30 }31 }32 return ans;33 }34 };35 matrix powM(matrix a, int b) {36 matrix ans = matrix();37 for (int i = 0; i <= m; i++)38 ans.cnt[i][i] = 1;39 while (b) {40 if (b & 1)41 ans = ans * a;42 a = a * a;43 b /= 2;44 }45 return ans;46 }47 int main() {48 matrix g, ans, dp = matrix();49 scanf("%lld%lld%lld", &n, &m, &mod);50 scanf("%s", s);51 getN(m);52 Next[0] = 0;53 memset(g.cnt, 0, sizeof(g.cnt));54 for (int i = 0; i < m; i++) {55 for (int j = '0'; j <= '9'; j++) {56 int t = i;57 while (t&& s[t] != j)58 t = Next[t];59 if (s[t] == j)60 t++;61 g.cnt[i][t]++;62 }63 }64 dp.cnt[0][0] = 1;65 ans = powM(g, n);66 ans = dp * ans;67 ll sum = 0;68 for (int i = 0; i < m; i++)69 sum = (sum + ans.cnt[0][i]) % mod;70 printf("%lld\n", sum);71 }