网站seo优化的重要性,手机平台,营销网站系统,做网站学习题意#xff1a;给你a串和b串#xff0c;你能切k次#xff0c;每次切完将尾部分放在头的前面#xff0c;问有多少种方案切k次从a串变为b串 思路#xff1a;令dp[i][0]为砍了i次变成b串的方案数#xff0c;dp[i][1]为砍了i次变成非b串的方案数#xff0c;然后预处理一下前… 题意给你a串和b串你能切k次每次切完将尾部分放在头的前面问有多少种方案切k次从a串变为b串 思路令dp[i][0]为砍了i次变成b串的方案数dp[i][1]为砍了i次变成非b串的方案数然后预处理一下前缀就可以DP了 #includebits/stdc.h
using namespace std;
const int mod 1e97;
#define LL long long
LL dp[300000][2];
int main()
{string a,b;int k;cin a b k;int lena a.size();int lenb b.size();if (ab)dp[0][0]1;else dp[0][1]1;int x 0;for (int i 0;ilena;i){int flag 1;for (int j 0;jlena;j){if (a[(ij)%lena] ! b[j]){flag 0;break;}}if (flag)x;}for (int i 0;ik;i){dp[i1][0](x*dp[i][1](x-1)*dp[i][0])%mod;dp[i1][1]((lena-x)*dp[i][0](lena-x-1)*dp[i][1])%mod;}printf(%d\n,dp[k][0]);
}Description Lets consider one interesting word game. In this game you should transform one word into another through special operations. Lets say we have word w, lets split this word into two non-empty parts x and y so, that w xy. A split operation is transforming wordw xy into word u yx. For example, a split operation can transform word wordcut into word cutword. You are given two words start and end. Count in how many ways we can transform word start into word end, if we apply exactlyksplit operations consecutively to word start. Two ways are considered different if the sequences of applied operations differ. Two operation sequences are different if exists such number i (1 ≤ i ≤ k), that in the i-th operation of the first sequence the word splits into parts x and y, in the i-th operation of the second sequence the word splits into parts a and b, and additionally x ≠ a holds. Input The first line contains a non-empty word start, the second line contains a non-empty word end. The words consist of lowercase Latin letters. The number of letters in word start equals the number of letters in word end and is at least 2 and doesnt exceed 1000 letters. The third line contains integer k (0 ≤ k ≤ 105) — the required number of operations. Output Print a single number — the answer to the problem. As this number can be rather large, print it modulo 1000000007(109 7). Sample Input Input ab
ab
2Output 1Input ababab
ababab
1Output 2Input ab
ba
2Output 0Hint The sought way in the first sample is: ab → a|b → ba → b|a → ab In the second sample the two sought ways are: ababab → abab|ab → abababababab → ab|abab → ababab 转载于:https://www.cnblogs.com/q934098774/p/5388694.html
