CF1778D - Flexible String Revisit

· · 题解

CF1778D - Flexible String Revisit

https://codeforces.com/contest/1778/problem/D

题意

给出两个长度均为 n(n\leq 10^6) 的 01 串 S 和 T。

每次随机将 S 中的某一位取反。

问：第一次 S = T 时操作次数的期望。

思路

显然，我们只关心当前 S 与 T 有几个位置不同。

用 f_i 表示当前有 i 个位置不同，从当前状态到 S = T 操作次数的期望。

转移方程：

f_i = \begin{cases} 0 &,i=0 \\ f_{n-1}+1 &,i=n\\ f_{i+1}\times(1-\frac{i}{n})+f_{i-1}\times \frac{i}{n}+1 &,1\leq i\leq n-1\\ \end{cases}

显然，此转移方程存在环。 如何处理？

不妨从 1\leq i\leq n-1 时下手，将这个方程改写成一般的线性递推式。

当 1\leq i\leq n-1 时，

f_i=f_{i+1}\times(1-\frac{i}{n})+f_{i-1}\times \frac{i}{n}+1 \quad,1\leq i\leq n-1

可以改写成一般的线性递推式：

f_i=\frac{f_{i-1}-f_{i-2}\times \frac{i-1}{n}-1}{1-\frac{i-1}{n}} \quad,2\leq i \leq n

因为 f_0=0，所以 i=2 时有：

f_2=\frac{f_1-f_0\times \frac{i-1}{n}-1}{1-\frac{i-1}{n}}=\frac{f_1-0-1}{1-\frac{i-1}{n}}

由此不难发现，f_i 的每一项都可以改写成如下形式：

f_i=p_i\times f_1+q_i

注意到：

f_n=f_{n-1}+1 f_n-f_{n-1}=1 p_n\times f_1+q_n - (p_{n-1}\times f_1+q_{n-1})=1 **如何递推 $p_i$ 和 $q_i$？** 观察递推式：$f_i=\frac{f_{i-1}-f_{i-2}\times \frac{i-1}{n}-1}{1-\frac{i-1}{n}} \quad 
注意到分子的 $-1$ 是常数，他只应该作用在常数 $q$ 上。
也就是：
$p_i=\frac{p_{i-1}-p_{i-2}\times \frac{i-1}{n}}{1-\frac{i-1}{n}},q_i=\frac{q_{i-1}-q_{i-2}\times \frac{i-1}{n}-1}{1-\frac{i-1}{n}}$。

最后，答案就是 f_x=p_x\times f_1+q_x，其中 x 是 S 和 T 不同的位置数量。

void Sol()
{
    vector< pair<int,int> > dp(n+5);

    dp[0] = {0, 0};
    dp[1] = {1, 0};

    for (int i=2; i<=n; i++)
    {
        int inv = Div(i-1, n);
        // 递推 pi, qi
        dp[i].first = Div(((dp[i-1].first-(dp[i-2].first*inv%MOD)+MOD)%MOD+MOD)%MOD, (1-inv+MOD)%MOD);
        dp[i].second = Div(((dp[i-1].second-(dp[i-2].second*inv%MOD)+MOD)%MOD-1+MOD)%MOD, (1-inv+MOD)%MOD);
    }
    // 求解 f1
    int p = (dp[n].first-dp[n-1].first+MOD)%MOD;
    int q = (dp[n].second-dp[n-1].second+MOD)%MOD;
    int t = Div((1-q+MOD)%MOD, p);

    int cnt = 0;
    for (int i=1; i<=n; i++)
        cnt += (S[i] != T[i]);

    int ans = (dp[cnt].first*t%MOD + dp[cnt].second)%MOD;
    printf("%lld\n", ans);
}