CF176B Word Cut

题意：定义一***作：对于一个串，从任意地方截断，然后把两部分位置交换得到新的串。

对于aa 串一共进行kk 轮这种操作。

问从aa 串变到bb 串有多少种方法。

f数组定义为操作n次是否变成原串的方案数
需要算出s1经过多少种方式能变成s2
这里有个技巧，如果某个串与目标串不同，他有x次可以转化为目标串，那么目标串有x-1次转化为目标串。

#include<iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll f[100010][2];//经过i次变换（0/1）（原串/其他串）
	string s1,s2;
bool check(int l,int r)
{
   
	int p=0;
	for(int i=l;i<=r;i++)
		if(s1[i]!=s2[++p])
			return 0;
		return 1;
}
int main()
{
   
	ll k;
	cin>>s1>>s2;
	int len=s1.size();
	bool flag=(s1==s2);
	s1+=s1;
	s1=' '+s1;
	s2=' '+s2;
	cin>>k;
	int cnt=0;
	for(int i=1	;i<=len;i++)
		if(check(i,i+len-1))
			cnt++;
	if(flag)
		f[0][0]=1;
	else
		f[0][1]=1;
	for(int i=1;i<=k;i++)
	{
   
		f[i][0]=(f[i-1][0]*(cnt-1)+ f[i-1][1]*cnt)%mod;
		f[i][1]=(f[i-1][0]*(len-cnt) + f[i-1][1]*(len-1-cnt) )%mod;
	}
	cout<<f[k][0]<<endl;
	return 0;
}