CodeForces 176B - Word Cut 计数DP

时间：2022-01-04 22:18:58
B. Word Cut
 

Let's consider one interesting word game. In this game you should transform one word into another through special operations.

Let's say we have word w, let's split this word into two non-empty parts x and y so, that w = xy. A split operation is transforming wordw = xy into word u = yx. For example, a split operation can transform word "wordcut" into word "cutword".

You are given two words start and end. Count in how many ways we can transform word start into word end, if we apply exactly k splitoperations consecutively to word start.

Two ways are considered different if the sequences of applied operations differ. Two operation sequences are different if exists such number i (1 ≤ i ≤ k), that in the i-th operation of the first sequence the word splits into parts x and y, in the i-th operation of the second sequence the word splits into parts a and b, and additionally x ≠ a holds.

Input

The first line contains a non-empty word start, the second line contains a non-empty word end. The words consist of lowercase Latin letters. The number of letters in word start equals the number of letters in word end and is at least 2 and doesn't exceed 1000 letters.

The third line contains integer k (0 ≤ k ≤ 105) — the required number of operations.

Output

Print a single number — the answer to the problem. As this number can be rather large, print it modulo 1000000007 (109 + 7).

Sample test(s)
input
ab
ab
2
output
1
input
ababab
ababab
1
output
2
input
ab
ba
2
output
0
Note

The sought way in the first sample is:

ab  →  a|b  →  ba  →  b|a  →  ab

题意：

给定一个串A,B，正好执行K次操作，每次操作可以把 A串从中间切开，并调换两部分的位置，问最后得到B串共有多少种不同的切法（只要中间有一次不同，即视为不同）

题解：

设定DP[i][0] i次操作后 是B串 的个数

　　DP[i][1] i次操作后非B串的个数

　　我们先找出任意由A循环（当成一个环）一个串至多能 转化成B串的数量x

　　那么 从dp[i-1][0] 上一次操作的B串数量 可以再次转化成B串的数量就是  (x-1) * dp[i-1][0];那么从上一次操作由非B串转化成B串的数量是 （已经求好）  x*(dp[i-1][1]) 

　　那么类似计数法 求dp[i][1] 转换到K就好了

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include<vector>

using namespace std ;

typedef long long ll;

const int  N =  + ;

const int mod = 1e9 + ;

ll dp[N][]; // [i][0]经过i次转换 是B串的个数 // [i][1]经过i次转换 是原串的个数

int main() {

    char a[N],b[N];

    int k;

    scanf("%s%s%d",a,b,&k);

    int len = strlen(a);

    ll x = ,sum;

    for(int i =  ; i < len; i++) {

            sum = ;int cnt= ;

        for(int j = i ;j < len; j++) {

            if(a[j] != b[cnt++]) sum++;

        }

        for(int j =  ;j < i; j++) if(a[j] != b[cnt++]) sum++;

        if(!sum) x++;

    }

    if(strcmp(a,b) == ) dp[][] = ;

    else dp[][] = ;

    for(int i=;i<k;i++)

    {

        dp[i+][]=(x*dp[i][]+(x-)*dp[i][])%mod;

        dp[i+][]=((len-x)*dp[i][]+(len-x-)*dp[i][])%mod;

        printf("%I64d %I64d\n",dp[i][],dp[i][]);

    }

    printf("%I64d\n",dp[k][]);

    return ;

}

相关文章