算法1

(状态机dp) $O(k+n*n)$

将整个字符串首尾相接，形成一个环，这样每进行一次分割再拼接操作，等价于找环的间隔位置
这里很容易有向直接推式子计算的想法，但却不可以。因为当选定当前的切割位置时，下一次就不可以再切割当前的位置了。也就是说，当前在哪个位置切割会影响下一个位置在哪里切割。因此不可以直接推式子，应当dp计算

dp数组状态见代码注释

由于对于某一次切割时，每个位置都不相同，且当前切割的次数也不同，所以可以用乘法原理直接计算下一次切割的方案数。

C++ 代码

#include <bits/stdc++.h>
//#define int long long 
#define INF 0x3f3f3f3f
#define fr first
#define se second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;

string a,b;
int k;

void solve()
{
    cin>>a>>b;
    cin>>k;
    int cnt = (a==b);//正确切割位置的数量
    int len = a.size();
    for(int i=len-1;i>=1;i--)
    {
        cnt += (a.substr(i)+a.substr(0,i) == b);
    }
    vector<vector<int>> dp(k+1,vector<int>(2,0));
    //dp[i][0]表示对a进行恰好i次操作，与b相同的方案数
    //dp[i][1]表示对a进行恰好i次操作，与b不相同的方案数
    if(a==b) dp[0][0]=1;
    else dp[0][1]=1;

    for(int i=1;i<=k;i++)
    {
        dp[i][0] = (1ll * (cnt-1) * dp[i-1][0] + 1ll * cnt * dp[i-1][1]) % MOD;
        dp[i][1] = (1ll * (len-cnt) * dp[i-1][0] + 1ll * (len-cnt-1) * dp[i-1][1]) % MOD;
    }
    cout << dp[k][0] << endl;
}


signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1; //cin>>T;
    while(T--) solve();
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla