题解 P9142 【[THUPC 2023 初赛] 欺诈游戏】

Leasier · 2023-03-20 16:33:13 · 题解

设走私者放 i 元的概率为 f(i)，检察官猜 i 元的概率为 g(i)，则：

• 走私者放 i 元时，走私者的期望收益为 E_1(i) = i \displaystyle\sum_{j = 0}^{i - 1} g(j) + \frac{1}{2} \sum_{j = i + 1}^n j g(j)。
• 检察官猜 i 元时，走私者的期望收益为 E_2(i) = \frac{i}{2} \displaystyle\sum_{j = 0}^{i - 1} f(j) + \sum_{j = i + 1}^n j f(j)。

这里我们以第一个式子为例（第二个式子的后续推导与之相似）。

下面是一个小但我之前不会的套路。

注意到“你需要保证，在一方的策略不变的情况下，另一方无论如何改变自己的策略，都不能使自己的期望收益比原来多。”，考虑调整法，设 \Delta g(i) = g'(i) - g(i) 表示对走私者策略进行调整的幅度——显然有 \displaystyle\sum_{i = 0}^n \Delta g(i) = 0。

然后有 \displaystyle\sum_{i = 0}^n \Delta g(i) E_1(i) \leq 0 恒成立。假如我们抓出 E_1(i) 中最大者并给它整一个很大的 \Delta g(i)，若此时 E_1(i) 不两两相等，则一定存在一种 \Delta g(i) 使之不合法，于是我们得出了本题最关键的结论：

考虑抓出比较像的相邻两项来讨论，下面假定我们讨论 E_1(i) = E_1(i + 1)：

进行化简后可得：

于是我们可以将所有 g(i) 表示为 g(0) 的倍数，又因为 \displaystyle\sum_{i = 0}^n g(i) = 1，我们将系数代入求出 g(0) 即可得出所有 g(i)。

同理可得：f(i) = \dfrac{(i - 1) f(i - 1) + \displaystyle\sum_{j = 0}^{i - 1} f(j)}{2i}。

线性求逆即可。时间复杂度为 O(n)。

代码：

#include <stdio.h>

typedef long long ll;

const int mod = 998244353;
ll inv[800007], f[400007], g[400007];

inline void init(int n){
    inv[0] = inv[1] = 1;
    for (register int i = 2; i <= n; i++){
        inv[i] = mod - (mod / i) * inv[mod % i] % mod;
    }
}

inline ll quick_pow(ll x, ll p, ll mod){
    ll ans = 1;
    while (p){
        if (p & 1) ans = ans * x % mod;
        x = x * x % mod;
        p >>= 1;
    }
    return ans;
}

int main(){
    int n;
    ll pre = 0, sumf = 0, sumg = 0;
    scanf("%d", &n);
    init(n * 2);
    f[0] = 1;
    for (register int i = 1; i <= n; i++){
        pre = (pre + f[i - 1]) % mod;
        f[i] = (f[i - 1] * (i - 1) % mod + pre) % mod * inv[i * 2] % mod;
    }
    for (register int i = 0; i <= n; i++){
        sumf = (sumf + f[i]) % mod;
    }
    sumf = quick_pow(sumf, mod - 2, mod);
    for (register int i = 0; i <= n; i++){
        printf("%lld ", f[i] * sumf % mod); 
    }
    printf("\n");
    pre = 0;
    g[0] = 1;
    for (register int i = 1; i <= n; i++){
        pre = (pre + g[i - 1]) % mod;
        g[i] = (g[i - 1] * (i - 1) % mod + pre) % mod * 2 % mod * inv[i] % mod;
    }
    for (register int i = 0; i <= n; i++){
        sumg = (sumg + g[i]) % mod;
    }
    sumg = quick_pow(sumg, mod - 2, mod);
    for (register int i = 0; i <= n; i++){
        printf("%lld ", g[i] * sumg % mod); 
    }
    return 0;
}