[Codeforces 176B]Word Cut

Description

题库链接

给你两个字符串 (S) 和 (T) ，准许你 (k) 次操作，每次将字符串左右分成两个非空的部分，再交换位置，问你有多少种不同的操作方法将 (S) 串变为 (T) 串。

(1leq kleq 100000, 1leq |S|=|T|leq 1000)

Solution

容易发现不论经过多少次操作，其操作后的字符串一定是在原字符串上截开两段再拼接而成。

所以不妨记 (f_{i,j}) 为操作 (i) 次后在 (j) 处截开的方案数为 (f_{i,j}) 。

转移就是由 (i-1) 中所有 ( eq j) 的位置转移过来的。

但复杂度是 (O(|S|k)) 的，不太优雅。但其实考虑到所有字符串本质只有与 (T) 串相不相同的两种情况，我们不妨记 (f_{i,0/1}) 表示操作 (i) 次后与 (T) 串是否相同的方案数为 (f_{i,j}) 。

这样就可以线性转移了。但是要先 (O(|S|^2)) 预处理出 (same) ，表示多少个位置断开与 (T) 串本质相同。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1000, yzh = 1e9+7;

char s[N+5], t[N+5];
int same, len, f[N*100+5][2], k;

bool check(int x) {
    for (int i = 1; i <= len; i++) {
    if (s[x] != t[i]) return false;
    ++x; if (x > len) x = 1;
    }
    return true;
}
void work() {
    scanf("%s%s", s+1, t+1); len = strlen(s+1); scanf("%d", &k);
    for (int i = 1; i <= len; i++)
    if (check(i)) ++same;
    if (check(1)) f[0][0] = 1; else f[0][1] = 1;
    for (int i = 1; i <= k; i++) {
    f[i][0] = (1ll*f[i-1][0]*(same-1)%yzh+1ll*f[i-1][1]*same%yzh)%yzh;
    f[i][1] = (1ll*f[i-1][0]*(len-same)%yzh+1ll*f[i-1][1]*(len-same-1)%yzh)%yzh;
    }
    printf("%d
", f[k][0]);
}
int main() {
    work(); return 0;
}