ABC280E数学期望DP逆元（倒搜）

#include <stdio.h>
const int mo=998244353, ni=828542813;
int n, m, i, j, k, f[200005];
int mi(long long a, int b){
    int s=1, i;
    while(b){
        if(b&1) s = s * a % mo;
        b /= 2, a = a * a % mo;
    }
    return s;
}//除法取模，转化成乘以除数的逆元
int dfs(int n){
    if(n < 1) return 0;
    if(f[n] != -1) return f[n];
    int s = 1ll * dfs(n-2) * m % mo * ni % mo;//m/100的概率到n-2
    s += dfs(n-1) * (100ll-m) % mo * ni % mo;//(100-m)/100的概率到n-1
    return f[n] = ++s%mo;//需要加1次操作
}
int main(){
//  printf("%d\n", 82854281300%mo);//检查逆元
//  return mi(100, mo-2);//预处理100的逆元
    scanf("%d%d", &n, &m);
    for(i=0; i<=n; i++) f[i] = -1;
    printf("%d\n", dfs(n));
    return 0;
}