Word Cut

一道cf的dp题,也挺好的,虽然没牛客难..牛客还是牛/..
这题是可以选择单词断开然后连起来,类似环.
考虑dp,令dp[0][i]为操作i次是原串的方案数,dp[1][i]为操作i次是其他串的方案数.
然后显然就有两个dp方程.

dp[0][i]=dp[1][i-1]*(n-1).
dp[1][i]=dp[0][i-1]+dp[1][i-1]*(n-2).

然后比较下两个串,对第二个串看成环进行考虑,假如开始相同就是+dp[0][k],不然就是+dp[1][k].

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int mod=1e9+7;
typedef long long ll;
ll dp[N][N],ans=0;
int main()
{
    string s,t;
    cin>>s>>t;
    int n=s.size();
    int k;
    scanf("%d",&k);
    dp[0][0]=1;
    dp[1][0]=0;
    for(int i=1;i<=k;i++)
    {
        dp[0][i]=dp[1][i-1]*(n-1)%mod;
        dp[1][i]=(dp[0][i-1]+dp[1][i-1]*(n-2))%mod;
    }
    bool flag;
    for(int i=0;i<n;i++)//设偏移多少.
    {
        flag=true;
        for(int j=0;j<n;j++)
        {
            if(s[(i+j)%n]!=t[j]) flag=0;
        }
        if(flag)
        {
            if(i==0) ans+=dp[0][k];
            else     ans+=dp[1][k];
            ans%=mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}