ABC298E概率期望快速幂倒搜

#include <stdio.h>
#include <string.h>
const int N=105, mo=998244353;
int n, m, i, j, k, a, b, p, q, P, Q, f[2][N][N];
int mi(long long a, int b){
    int s = 1;
    while(b){
        if(b&1) s = s*a % mo;
        a = a*a % mo, b /= 2;
    }
    return s;
}
int dfs(int k, int a, int b){
    if(a>=n || b>=n) return k;
    if(~f[k][a][b]) return f[k][a][b];
    int i, s=0;
    if(k&1){
        for(i=1; i<=q; i++){
            s = (s + 1ll * dfs(k^1, a, b+i) * Q) % mo;
        }//1/q的概率，乘以q的逆元Q即可
    }
    else{
        for(i=1; i<=p; i++){
            s = (s + 1ll * dfs(k^1, a+i, b) * P) % mo;
        }
    }
    return f[k][a][b] = s % mo;
}
int main(){
    scanf("%d%d%d%d%d", &n, &a, &b, &p, &q);
    P = mi(p, mo-2), Q = mi(q, mo-2);
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(0, a, b));
    return 0;
}