Codeforces 176B Word Cut 题解

题目链接： Codeforces 176B Word Cut

---

题目大意

给两个字符串 \(s\)，\(e\) \((\text{len} \leq 1000)\)，和数字 \(k\) \((k\leq 10^5)\)， 定义一次操作为：从当前字符串中任取一个间隔拆开字符串并交换左右部分得到新字符串，问从 \(s\to e\) 且恰好操作了 \(k\) 次的不同方案数。

题解

1. 我们把字符串复制一份放到后面接上，设为 \(t=s+s\) ，则每一次操作实际上是取字符串 \(t\) 的一个长为 \(n\) 的子串得到新串，所以我们可以直接得到在所有的 \(n\) 个循环串（设为集合 \(T\)）中哪些是最终状态 \(e\)，并记录满足条件的位置（记为 \(O\)）个数为 \(\text{ok}\)，则不能达到的状态位置个数 \(\text{nok}=n-\text{ok}\).

2. 注意到每考虑一次该操作，即代表一个从 \(T\to T\) 的映射，我们发现当前操作中达到某一个 \(e\) 位置的方案可以由上一次操作转移，由于转移中可能用到中间过渡的非终点串，于是设 \(\text{dp}[0][i]\) 表示进行了 \(i\) 次操作后达到 \(O\) 的方案数，\(\text{dp}[1][i]\) 为 进行了 \(i\) 次操作后达到 \(T-O\) 的方案数，

   则有： \[ \begin{aligned} \text{dp}[0][i] &= \text{dp}[0][i-1]\times(\text{ok}-1)+\text{dp}[1][i-1]\times(\text{ok}) \\ \text{dp}[1][i] &=\text{dp}[0][i-1]\times (\text{nok}) +\text{dp}[1][i-1]\times (\text{nok} - 1) \end{aligned} \]

   该转移表示，当前的到达终点串的方案一方面来自上次状态的到达终点的方案转移到新的终点串，由于每次转移不能转移到自己，故为 \(\text{ok}-1\)，而另一部分为上一个状态中不能到达终点串的方案再利用所有终点串转移到当前状态，故直接为 \(\text{ok}\)。当前状态的非终点串方案同理。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for (c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

const int N = 1e3 + 5;
const int K = 1e5 + 5;
const int MOD = 1e9 + 7;

int n, k;
string s, e;
ll ok, nok, dp[2][K];

int main() {
    // freopen("t5.in", "r", stdin);
    cin >> s >> e >> k;
    n = s.length();
    string t = s + s;
    for(int i = 0; i < n; i++) {
        string _t = t.substr(i, n);
        if(_t == e) ok++;
        else nok++; 
    }
    // cout << ok << endl;
    if(s == e) dp[0][0] = 1;
    else dp[1][0] = 1;
    for(int i = 1; i <= k; i++) {
        dp[0][i] = (dp[1][i - 1] * ok % MOD + dp[0][i - 1] * (ok - 1) % MOD) % MOD;
        dp[1][i] = (dp[1][i - 1] * (nok - 1) % MOD + dp[0][i - 1] * nok % MOD) % MOD;
    }
    cout << dp[0][k] << endl;
    return 0;
}