AcWing1052设计密码(IndeedTokyo2019校招笔试题)(kmp+dp)
程序员文章站
2022-05-04 11:58:13
题目链接题目描述你现在需要设计一个密码 S,S 需要满足:S 的长度是 NS 只包含小写英文字母S 不包含子串 T例如:abc 和 abcde 是 abcde 的子串,abd 不是 abcde 的子串。请问共有多少种不同的密码满足要求?由于答案会非常大,请输出答案模 109+7 的余数。f[i][j]f[i][j]f[i][j]定义到第i位密码位置与子串T匹配长度为j时的密码数目。要求的答案为∑j=0m−1f[N][j]\sum_{j=0}^{m-1}f[N][j]j=0∑m−1...
题目描述
你现在需要设计一个密码 S,S 需要满足:
- S 的长度是 N
- S 只包含小写英文字母
- S 不包含子串 T
例如:abc 和 abcde 是 abcde 的子串,abd 不是 abcde 的子串。
请问共有多少种不同的密码满足要求?
由于答案会非常大,请输出答案模 109+7 的余数。
定义到第i位密码位置与子串T匹配长度为j时的密码数目。
要求的答案为
其中为禁止串长度。
这是一个状态机问题。
首先对于加在第位的字母有26个选择,对于不同字母的选择,假定当前状态为(第位为止与串匹配的长度为),其下一个状态(即加上这个字母后与串匹配的长度)我们定义为(类似于有穷状态自动机的东西),那么我们就可以得到状态转移的方程
只需要提前预处理出即可。
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
char T[60];
int nxt[60], dfa[60][60];
LL f[60][60];
int main() {
int n, m;
cin >> n;
cin >> (T+1);
m = strlen(T+1);
for (int i = 2, j = 0; i <= m; i++) {
while(j && T[j+1] != T[i]) j = nxt[j];
if (T[j+1] == T[i]) j++;
nxt[i] = j;
}
// 不预处理dfa也可,效率会低一些。
for (int j = 0; j < m; j++) {
for (int k = 0; k < 26; k++) {
int t = j;
while (t && T[t+1] != k + 'a') t = nxt[t];
if (T[t+1] == k + 'a') t++;
dfa[j][k] = t;
}
}
f[1][0] = 25, f[1][1] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < 26; k++) {
// 利用dfa进行状态转移
f[i+1][dfa[j][k]] = (f[i+1][dfa[j][k]] + f[i][j]) % mod;
}
}
}
LL res = 0;
for (int i = 0; i < m; i++) res = (res + f[n][i]) % mod;
cout << res << endl;
return 0;
}
本文地址:https://blog.csdn.net/weixin_43359565/article/details/107611073
上一篇: 网站优化被K了该怎么解决