题目描述

操作等价于向左移动，
那么其实就是求某个位置能不能左移变成目标字符串
假设有cnt个位置可以左移变成目标字符串
那么就有n-cnt个位置移动是变成不了的
所以直接dp[i][0/1]进行前i次操作
0代表当前不是目标字符，1代表是目标字符

dp[i-1][0]可以通过n-cnt-1个位置变成
dp[i-1][0]
因为有n-cnt个位置不能变成目标字符，
且因为当前不是目标字符，说明当前位置就是一个不合法的操作后的结果，所以要减去一个位置，其他同理

优化的话可以通过Z函数去找合法左移位置，操作可以通过矩阵快速幂变成log(k)复杂度

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=N*2,mod=1e9+7;
#define int long long
#define uLL unsigned long long
const long long inf=1e18;
const long long INF=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
int S,T;
int f[N][5];
void solve()
{
    //先把s变成t
    string s1,s2;
    cin>>s1>>s2>>m;
    int n=s1.size();
    int cnt=0;
    s1+=s1;
    for(int i=1;i<s1.size();i++){
        if(s1.substr(i,n)==s2){
            cnt++;
        }
    }
    if(cnt==0){
        cout<<0;return ;
    }
    //cout<<cnt<<"\n";
    //cnt个位置可以复原 n-cnt个不可以
    if(s1.substr(0,n)==s2) f[0][1]=1;
    else f[0][0]=1;
    for(int i=1;i<=m;i++){
        f[i][0]=f[i-1][0]*(n-cnt-1)%mod+f[i-1][1]*(n-cnt)%mod;
        f[i][0]%=mod;
        f[i][1]=f[i-1][0]*cnt%mod+f[i-1][1]*(cnt-1)%mod;
        f[i][1]%=mod;
    }
    cout<<f[m][1];
}   
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2,M=N*2,mod=1e9+7;
#define int long long
#define uLL unsigned long long
const long long inf=1e18;
const long long INF=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
int S,T;

void mul(int c[], int a[], int b[][N])
{
    int temp[N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % mod;

    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
    int temp[N][N] = {0};
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            for (int k = 0; k < N; k ++ )
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % mod;

    memcpy(c, temp, sizeof temp);
}

void solve()
{
    //先把s变成t
    string s1,s2;
    cin>>s1>>s2>>m;
    int n=s1.size();
    int cnt=0;
    string s=s2+s1+s1;
    vector<int> z(n+n+n);
    int l=0,r=0;
    for (int i = 1; i < n+n+n; i++) 
    {
        if (i <= r) {
            z[i] = min(z[i - l], r - i + 1);
        }
        while (i + z[i] < n+n+n && s[z[i]] == s[i + z[i]]) {
            l = i;
            r = i + z[i];
            z[i]++;
        }
    }

    for(int i=n;i<n+n;i++){
        if(z[i]>=n) cnt++;
    }
    //cout<<cnt<<"\n";
    //cnt个位置可以复原 n-cnt个不可以

    //cout<<cnt<<"\n";
    int f[2]={0,0};
    if(s1.substr(0,n)==s2) f[1]=1;
    else f[0]=1;
    int a[2][2] = {
        {n-cnt-1,cnt},
        {n-cnt,cnt-1},
    };

    while (m)
    {
        if (m & 1) mul(f, f, a);  
        mul(a, a, a); 
        m >>= 1;
    }
    cout<<f[1]<<"\n";
}   
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
}