1778D Flexible String Revisit

目录
1778D Flexible String Revisit
题目大意：
做法：
dp
注意
code

题目大意：

给你两个长度均为\(n\)二进制数列：\(S,T\) 每次可以把\(S\)中的一位取反，问你\(S \to T\)的期望方案数。

做法：

dp

我们考虑\(dp_i\)表示\(i\)个不一样的位置\(\to i - 1\)个不一样的位置的期望方案数

每次有\(\dfrac{i}{n}\)的概率翻转一个未匹配字符，\(\dfrac{n - i}{n}\)的概率翻转一个已匹配字符。翻转到已匹配字符需要 \(f_{i + 1}\)期望次数才能回到当前状态，然后又需要\(f_i\)期望次数才能翻转一个未匹配字符。于是有方程：

\(f_i = 1 + \dfrac{n - i}{n} * (f_{i + 1} + f_i)\)

化简一下：

\(f_i = \dfrac{n + (n - i) * f_{i + 1}}{i}\)

注意

当所有字符未匹配时随意翻一个都是未匹配字符，所以\(f_n = 1\)

设初始状态有\(k\)个字符需要匹配，那么\(ans = \sum_{i = 1}^{x}\)

code

#include<bits/stdc++.h>

using namespace std;

const long long mod = 998244353;

const int N = 1e6 + 5;

int n;

char s[N] , t[N];

long long fac[N + 5] , inv[N + 5] , ans , f[N] , p;

long long ksm (long long x , long long y) {

    if(!y)

        return 1;

    long long z = ksm (x , y / 2);

    z = z * z % mod;

    if (y & 1)

        z = z * x % mod;

    return z;

}

void pre () {

    fac[0] = 1;

    for (int i = 1 ; i <= N ; i ++) {

        fac[i] = fac[i - 1] * i % mod;

    }

    inv[N] = ksm(fac[N] , mod - 2);

    for (int i = N - 1 ; i >= 0 ; i --) {

        inv[i] = inv[i + 1] * (i + 1) % mod;

    }

}

int main () {

    int T , dif;

    pre ();

    scanf ("%d" , &T);

    while(T --) {

        scanf ("%d" , &n);

        scanf("%s%s",s+1,t+1);

        dif = 0;

        for (int i = 1 ; i <= n ; i++) {

            if (s[i] != t[i]) {

                dif ++;

            }

        }

        inv[n] = ksm(n , mod - 2);

        f[n] = 1;

        for (int i = n - 1 ; i >= 1 ; i--) {

            f[i] = (n + (n - i) * f[i + 1] % mod) * ksm (i , mod - 2) % mod;

        }

        ans = 0;

        for (int i = 1 ; i <= dif ; i++) {

            ans = (ans + f[i]) % mod;

        }

        printf("%lld\n" , ans);

    }

    return 0;

}

1778D Flexible String Revisit的相关教程结束。