Codeforces Round 848 (Div. 2)——D题（期望DP）

======>题目链接

  本题的期望dp定义的f[i]表示到达有i个字符相等所需要的期望操作次数，不同于之前常见的定义方式(f[i]表示从i到n的期望值)。在此记录一下。

  因为本题如果f[i]定义为从有i个字符相等到n个字符相等的期望操作次数，那么转移方程为f[i] = (n - i) / n * f[i + 1] + i / n * f[i - 1]，那么就难以递推。因此需要改变一下状态的定义。

  上式中E(x - 1) + E[x] + 1代表从E[x - 1]变到E[x + 1]需要的期望次数，再加上之前消耗的那一次。

AC代码：

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

const int N = 1e6 + 10, MOD = 998244353;
char a[N], b[N];
int f[N], inv[N];
int n, cur, ans;

int qmi(int a, int k){
	int ans = 1;
	while(k){
		if(k & 1) ans = 1LL* ans * a % MOD;
		a = 1LL* a * a % MOD;
		k >>= 1;
	}
	return ans;
}

void init(){
	for(int i = 0; i < N; i++){
		inv[i] = qmi(i, MOD - 2);
	}
}


void solve(){
	scanf("%d", &n);
	scanf("%s%s", a + 1, b + 1);
	cur = ans = 0;
	for(int i = 0; i <= n; i++) f[i] = 0;
	for(int i = 1; i <= n; i++){
		if(a[i] == b[i]) cur++; 
	}
	f[0] = 1;
	for(int i = 1; i < n; i++){
		f[i] = (1 + 1LL* i * inv[n - i] % MOD * (1LL + f[i - 1]) % MOD) % MOD;
	}
	for(int i = cur; i < n; i++){
		ans = (1LL* ans + f[i]) % MOD;
	}
	printf("%d\n", ans);
}

int main(){
	init();
	int T = 1;
	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}