• 字符串
  • DP

【题意】

给定一个长度为 $n\le 1000$ 的字符串，再给定一个长度相等的目标串和非负整数 $k\le 10^5$，请问是否可以使用正好 $k$ 次操作，将原串变成目标串。

每一次操作选择一个位置 $p\in[1,n)$，然后将字符串变成 $[p+1,n]+[1,p]$。其中 $+$ 表示连接。

求操作方案数，取模。两个方案不同当且仅当至少有一步 $p$ 的选择不同。

【解析】

猜一个非常重要的结论：如果一次操作不行的话，那一定不行。

感性理解一下，字符之间的相对位置大体不变，一次不行的话多次也不行。

推广一下，也就是说做任意多次操作以后只需要做 $1$ 次操作就可以变成想要的样子。

所以我们可以先暴力求出一次操作能满足条件的方案数，记为 $\text{cnt}$。

则考虑 DP，设 $f_i$ 表示第 $i$ 步变成目标串的方案数，$g_i$ 表示第 $i$ 步没变成目标串的方案数。

推出转移方程 $f_i=cnt\times g_{i-1}+(cnt-1)\times f_{i-1}$。表示有 $\text{cnt}$ 种方式从上一个的任意非目标串状态变成目标串状态，$\text{cnt-1}$ 种方式从上一个的目标串再操作一次还是目标串。

类似地，$g_i=(n-cnt)\times f_{i-1}+(n-cnt-1)\times g_{i-1}$。

答案是 $f_k$，初始状态就是看看原串和目标串是否一样，是则 $f_0=1$，否则 $g_0=1$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1e5+10,mod=1e9+7;
string a,b,s,t;
int n,k;
ll f[N][2],cnt;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>s>>t>>k;
    n=s.size();
    if(k==0){
        if(s==t) cout<<1<<endl;
        else cout<<0<<endl;
        return 0;
    }
    if(s==t){
        cnt=1;
        f[0][0]=1;
    }
    else f[0][1]=1;
    F(i,1,n-1){
        a=s.substr(0,i);
        b=s.substr(i,n-i);
        a=b+a;
        if(a==t) cnt++;
    }
    F(i,1,k){
        f[i][0]=(cnt*f[i-1][1]+(cnt-1)*f[i-1][0])%mod;
        f[i][1]=((n-cnt)*f[i-1][0]+(n-cnt-1)*f[i-1][1])%mod;
    }
    cout<<f[k][0]<<endl;
    return 0;
}