视频题解
时间轴
大盗阿福 0:00
股票买卖 IV 2:15
股票买卖 V 4:55
设计密码 7:25
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve(){
const int mod = 1e9 + 7;
int n; string s; cin >> n >> s; s = " " + s;
int m = s.size() - 1;
vector<int> next(m + 1);
for(int i = 2, j = 0; i <= m; i ++){
while(j && s[i] != s[j + 1]) j = next[j];
if(s[i] == s[j + 1]) j ++;
next[i] = j;
}
vector<int> dp(m + 1);
dp[0] = 1;
for(int i = 0; i < n; i ++){
vector<int> t(m + 1);
for(int j = 0; j < m; j ++){
for(char k = 'a'; k <= 'z'; k ++){
int p = j;
while(p && k != s[p + 1]) p = next[p];
if(k == s[p + 1]) p ++;
if(p < m) t[p] = (t[p] + dp[j]) % mod;
}
}
dp = t;
}
int res = 0;
for(int i = 0; i < m; i ++) res = (res + dp[i]) % mod;
cout << res << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
while(T --){
solve();
}
}