题目描述

对于一个长度不小于 2 的字符串，我们可以对其使用重组操作。

重组操作分为两个步骤：

将字符串从中间任意位置截断，得到前后两个非空子串。
将两个子串交换位置（前变后，后变前）后重新连接，得到新字符串。
例如，对于字符串 abcdef，一种可行的重组操作为：

将字符串截断为两个非空子串 ab、cdef。
将两个子串交换位置后重新连接，得到新字符串 cdefab。
给定一个起始字符串 s1 和一个目标字符串 s2。

我们希望对 s1 进行恰好 k 次重组操作后得到 s2。

请你计算，一共有多少种不同的可行方案。

由于答案可能很大，请你输出对 10⁹+7 取模后的结果。

对于两种可行方案，如果存在至少一个 i（1≤i≤k）满足，在第 i 次操作中，两种方案的截断位置不同，则认为两种可行方案为不同方案。

输入格式
第一行包含一个由小写字母构成的非空字符串 s1。

第二行包含一个由小写字母构成的非空字符串 s2。

第三行包含整数 k。

输出格式
一个整数，表示不同的可行方案的数量对 10⁹+7 取模后的结果。

数据范围
前三个测试点满足 2≤|s1|,|s2|≤6，0≤k≤2。
所有测试点满足 2≤|s1|,|s2|≤1000，|s1|=|s2|，0≤k≤10⁵。

输入样例

ab
ab
2

输出样例

1

(动态规划) $O(k)$

可以s1看成一个环，寻找在哪里分割可以使s1转成s2，分割点的数量就是下文中的cnt(代码里是c)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int const N=100010,mod= 1e9 + 7,M=1010;
char s1[M*2],s2[M];
int k,len;
int f[N][2];
bool check(int start){
    for(int i=start,j=0;j<len;i++,j++)
        if( s1[i] != s2[j] ) return false;
    return true;
}
int main(){
    cin >> s1 >> s2 >> k;
    len=strlen(s1);
    for(int i = 0;i < len; i++ ) s1[len+i]=s1[i];
    int c=0;
    for(int i=0;i<len;i++) if(check(i)) c++;
    if(check(0)) f[0][0]=1;
    else f[0][1]=1;
    for(int i=1;i<=k;i++){
        f[i][0]=(f[i-1][0]*(LL)(c-1)+f[i-1][1]*(LL)c)%mod;
        f[i][1]=(f[i-1][0]*(LL)(len-c)+f[i-1][1]*(LL)(len-c-1))%mod;
    }
    cout << f[k][0];
return 0;
}