CF1778D Flexible String Revisit 题解

LinuF · 2023-05-12 19:56:00 · 题解

题意

给出两个长度均为 n 的 01 串 S 和 T。

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

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

思路

首先我们得目的是将两串不匹配的位置使得它能够匹配。

我们定义状态 f_{i} 意思为从剩余 i 个需要匹配的位置转移到到剩余 i-1 个，需要的次数的期望。

这个时候我们要从状态 i 转移到状态 i-1 的两种情况分析。

修改的位置恰好能匹配上，期望是 \frac{i}{n}。
修改的位置不能匹配上，那这个时候不匹配的个数会从 i 变成 i+1，期望是 \frac{n-i}{n}，那这个时候还要采用 f_{i+1} 来转移回 i，再从 i 转移到 i-1。

是能够证明只有这两种情况的，因为上下两个串要不然就是匹配，要不然就是不匹配，那修改要不然会改错，要不然就是改对了。

表现成状态转移方程是这样的：

f_{i}=\frac{n-i}{n}(1+f_{i+1}+f_{i})+\frac{i}{n}

化简过后会变成：

f_{i}=\frac{(n-i)dp_{i+1}+n}{i}

这样就能线性递推求解了，最后的答案 \sum_{i=1}^{\text{nums}}dp_{i}。

其中 \text{nums} 表示有多少位置没有匹配上。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
char a[N],b[N];
int n,dp[N],mod=998244353;
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1){
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}
int inv(int x){
    return qmi(x,mod-2);
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        cin>>(a+1)>>(b+1);
        int nums=0;
        for(int i=1;i<=n;i++){
            // cout<<a[i]<<" "<<b[i]<<endl;
            if(a[i]!=b[i]) nums++; 
        }
        for(int i=n;i>=1;i--){
            dp[i]=((n-i)*dp[i+1]%mod+n)*inv(i)%mod;
        }
        int res=0;
        for(int i=1;i<=nums;i++){
            res=(res+dp[i])%mod;
        }
        cout<<res<<endl;
    }
}