撰写时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 2 测试通过 : 0
比赛描述
看门老张从路边的魔术师那里买了一副纸牌，号称魔术纸牌。老张觉得自己只要能将这副纸牌玩个精通，一定能终结自己的单身生涯。每张纸牌上都标有一个小写字母，这一副n张纸牌从上至下就构成了一串字母。他想通过洗牌来将这一串字母变成另一串。但是老张所谓的洗牌就是把最下面的m张牌一起抽出然后放置在牌堆顶。比如原纸牌构成的字母串为dcbab，取最下面2张牌放在牌堆顶，即构成字母串abdcb。老张找到了号称资深僚机的你，他告诉你了原纸牌构成的字母串和他想得到的字母串，并且他想知道，经过k次这样的洗牌，有多少种方案可以将原纸牌构成的串变为这串他想得到的串。当然这个结果可能很大，所以需要将结果模1e9+7（1000000007）。
输入
输入包括三行，第一行为原始字母串，第二行为目标字母串，字母串均由小写字母组成，且原始字母串的长度等于目标字母串的长度，且至少为2，不超过1000个字母。第三行为一个整数k（0≤k≤10^5）代表所需的洗牌数。
输出
输出一个整数，代表所求的方案数对1e9+7的取模。
样例输入
ababab
ababab
1
样例输出
2
题解：看作一个环，把问题转换为从哪里切开的问题，解题的关键在于知道切成原串与切成目标串的区别在于第一刀不能切出原串（这里的原串指的不包括与原串相同的目标串），以及第一刀对后面的影响，从而得出原串与目标串的方法数，这里的目标串，其实可以看作“任意一个固定的目标串”。
状态转移：原串方法数为a，目标方法数为b，a[0] = 1, b[0] = 0,先假设原串与目标串不同，并且一个环里只有一个目标串出现。后一次的原串方法数要由上一次的任意目标串方法数去乘可以切的位置数（n-1，除上一次切的地方都可以），后一次的目标串方法数则是b*(n-1)-b+a(减去上一次切成方法数的再加上上一次的原串方法数)，也就是上次我有b种切法切成目标串，那我也有b种方法切为非目标串非原串，这次我有n-1种切法，但是要减去上次已经切好的情况，再加上从原串变过来的方法数。
如果原串与目标串相同，则在选择切为原串的方法数。否则可以切几次成为目标串，就加上几个b。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int mod = 1e9+7;
int N, ans, a, b, c, d, i;
bool flag;
string s, t;
int main()
{
cin>> s>> t>> N;
a = 1;
for(i = 1; i <= N; i++)
{
c = (1LL*b*(s.size()-1)) % mod;//b*(n-1)
d = (1LL*b*(s.size()-2)+a) % mod;//b*(n-1)-b+a
a = c; b = d;
}
for(i = 0; i < s.size(); i++)
{
flag = true;
for(int j = 0; j < t.size(); j++) if (s[(i+j)%s.size()] != t[j]) flag = false;//从i开始的串与目标串相同
if (flag && !i) ans = (ans+a)%mod;//原来就相同则加a
else if (flag) ans = (ans+b)%mod;//变换后才与目标串相同则加b
}
printf("%d\n", ans);
return 0;
}