P6858 數學期望

題意

傳送門 P6858 深海少女與胖頭魚

題解

設 A ( n , m ) A_{(n,m)} A(n,m)​ 代表初始時有 n n n 條帶聖盾的胖頭魚與 m m m 條不帶聖盾的胖頭魚，消滅胖頭魚的期望造成傷害次數。考慮進行一次傷害，則有狀态轉移

A ( n , m ) = 1 + m n + m A ( n , m − 1 ) + n n + m A ( n + m − 1 , 1 ) A_{(n,m)}=1+\frac{m}{n+m}A_{(n,m-1)}+\frac{n}{n+m}A_{(n+m-1,1)} A(n,m)​=1+n+mm​A(n,m−1)​+n+mn​A(n+m−1,1)​ 觀察 m = 0 m=0 m=0 的情況，此時有

A ( n , 0 ) = 1 + A ( n − 1 , 1 ) A_{(n,0)}=1+A_{(n-1,1)} A(n,0)​=1+A(n−1,1)​ 考慮進一步的狀态轉移 A ( n − 1 , 1 ) = 1 + 1 n A ( n − 1 , 0 ) + n − 1 n A ( n − 1 , 1 ) A_{(n-1,1)}=1+\frac{1}{n}A_{(n-1,0)}+\frac{n-1}{n}A_{(n-1,1)} A(n−1,1)​=1+n1​A(n−1,0)​+nn−1​A(n−1,1)​ 得到了一個遞歸的結構，則有

A ( n − 1 , 1 ) = n + A ( n − 1 , 0 ) A_{(n-1,1)}=n+A_{(n-1,0)} A(n−1,1)​=n+A(n−1,0)​ 将其帶入 m = 0 m=0 m=0 的遞推式，得到

A ( n , 0 ) = A ( n − 1 , 0 ) + n + 1 A_{(n,0)}=A_{(n-1,0)}+n+1 A(n,0)​=A(n−1,0)​+n+1 求解得到 m = 0 m=0 m=0 與 m = 1 m=1 m=1 情況下的閉合表達式

A ( n , 0 ) = ( n + 3 ) n / 2 , A ( n , 1 ) = ( n + 3 ) n / 2 + n + 1 A_{(n,0)}=(n+3)n/2,A_{(n,1)}=(n+3)n/2+n+1 A(n,0)​=(n+3)n/2,A(n,1)​=(n+3)n/2+n+1 在狀态 ( n , m ) (n,m) (n,m) 可能轉移到的兩種情況中，至少有一個可以通過閉合表達式求解，遞歸求解即可。總時間複雜度 O ( M ) O(M) O(M)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll N, M, inv2;

ll mod_pow(ll x, ll n)
{
    ll res = 1 % mod;
    x %= mod;
    while (n)
    {
        if (n & 1)
            res = res * x % mod;
        x = x * x % mod, n >>= 1;
    }
    return res;
}

ll solve(ll n, ll m)
{
    if (m <= 1)
    {
        ll res = m == 1 ? (n + 1) % mod : 0;
        res += (n + 3) % mod * (n % mod) % mod * inv2 % mod;
        return res % mod;
    }
    ll d = mod_pow(n + m, mod - 2);
    ll res = 1;
    res += m % mod * d % mod * solve(n, m - 1);
    res += n % mod * d % mod * solve(n + m - 1, 1) % mod;
    return res % mod;
}

int main()
{
    inv2 = mod_pow(2, mod - 2);
    cin >> N >> M;
    cout << solve(N, M) << '\n';
    return 0;
}