LOJ2325「清华集训2017」小Y和恐怖的奴隶主 <概率DP+矩阵快速幂>

Posted on 2018-07-13 Symbols count in article: 1.6k Reading time ≈ 6 mins.

Problem

「清华集训2017」小Y和恐怖的奴隶主

时间限制： $\mathrm{2000\;ms}$
内存限制： $\mathrm{256\;MiB}$

题目描述

"A fight? Count me in!" 要打架了，算我一个。
"Everyone, get in here!" 所有人，都过来！
$\mathrm{小Y}$ 是一个喜欢玩游戏的 $\mathrm{OIer}$ 。一天，她正在玩一款游戏，要打一个 $\mathrm{Boss}$ 。
虽然这个 $\mathrm{Boss}$ 有 $10^{100}$ 点生命值，但它只带了一个随从――一个只有 $m$ 点生命值的“恐怖的奴隶主”。
这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即 $生命值\le0$ ），且 $\mathrm{Boss}$ 的随从数量小于上限 $k$ ，便会召唤一个新的具有 $m$ 点生命值的“恐怖的奴隶主”。
现在 $\mathrm{小Y}$ 可以进行 $n$ 次攻击，每次攻击时，会从 $\mathrm{Boss}$ 以及 $\mathrm{Boss}$ 的所有随从中的等概率随机选择一个，并扣减 $1$ 点生命值，她想知道进行 $n$ 次攻击后扣减 $\mathrm{Boss}$ 的生命值点数的期望。为了避免精度误差，你的答案需要对 $998244353$ 取模。

输入格式

输入第一行包含三个正整数 $T,m,k$ ， $T$ 表示询问组数， $m,k$ 的含义见题目描述。
接下来 $T$ 行，每行包含一个正整数 $n$ ，表示询问进行 $n$ 次攻击后扣减 $\mathrm{Boss}$ 的生命值点数的期望。

输出格式

输出共 $T$ 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 $998244353$ 取模的结果。
可以证明，所求期望一定是一个有理数，设其为 $\frac{p}{q}$ （ $\gcd(p,q)=1$ ），那么你输出的数 $x$ 要满足 $p\equiv qx\bmod{998244353}$ 。

样例

输入

输出

1
2
3

499122177
415935148
471393168

解释
对于第一次询问，第一次攻击有 $\frac{1}{2}$ 的概率扣减 $\mathrm{Boss}$ 的生命值，有 $\frac{1}{2}$ 的概率扣减随从的生命值，所以答案为 $\frac{1}{2}$ 。 $1\equiv2\times499122177\bmod{998244353}$ 。
对于第二次询问，如果第一次攻击扣减了 $\mathrm{Boss}$ 的生命值，那么有 $\frac{1}{2}$ 的概率第二次攻击仍扣减 $\mathrm{Boss}$ 的生命值，有 $\frac{1}{2}$ 的概率第二次攻击扣减随从的生命值；如果第一次攻击扣减了随从的生命值，那么现在又新召唤了一个随从（“恐怖的奴隶主”），于是有 $\frac{1}{3}$ 的概率第二次攻击扣减 $\mathrm{Boss}$ 的生命值，有 $\frac{2}{3}$ 的概率第二次攻击扣减随从的生命值。所以答案为 $\frac{1}{2}\times\frac{1}{2}\times2+\frac{1}{2}\times\frac{1}{2}\times1+\frac{1}{2}\times\frac{1}{3}\times1+\frac{1}{2}\times\frac{2}{3}\times0 = \frac{11}{12}$ 。 $11\equiv12\times415935148\bmod{998244353}$ 。

数据范围与提示

在所有测试点中， $1\le T\le1000$ , $1\le n\le10^{18}$ , $1\le m\le3$ , $1\le k\le8$
各个测试点的分值和数据范围如下：

测试点编号	分值	$T$	$n$	$m$	$k$
$1$	$3$	$10$	$10$	$1$	$1$
$2$	$8$	$10$	$10$	$2$	$8$
$3$	$7$	$10$	$10^{18}$	$2$	$3$
$4$	$12$	$10$	$10^{18}$	$2$	$7$
$5$	$30$	$20$	$10^{18}$	$3$	$5$
$6$	$10$	$500$	$10^{18}$	$3$	$6$
$7$	$10$	$200$	$10^{18}$	$3$	$7$
$8$	$5$	$1000$	$10^{18}$	$3$	$7$
$9$	$10$	$100$	$10^{18}$	$3$	$8$
$10$	$5$	$500$	$10^{18}$	$3$	$8$

标签：概率DP 矩阵快速幂

Solution

这道题是BZOJ4832【Lydsy1704月赛】抵制克苏恩的加强版。与其相似，需要概率 $\mathrm{DP}$ 转移，因为 $n$ 很大而需要用矩阵快速幂优化。

考虑如何构造转移矩阵。转移矩阵相当于记录一个状态转移成另一个状态的概率。记状态 $(i,j,k)$ 表示血量为 $1,2,3$ 的奴隶主各有 $i,j,k$ 个的状态，则和弱化版相同，枚举打哪种奴隶主进行转移即可。然而有一种情况无法转移，即打脸的情况（对应 $f[i+1][a][b][c]=f[i][a][b][c]\times\frac{1}{a+b+c+1}$ ）。我们只需要给转移矩阵多开一行，存储 $\frac{1}{a_i+b_i+c_i+1}$ 即可。对应地，答案矩阵也需要多开一行，开始时这一行的数为 $1$ 。

注意：卡常！需要先预处理转移矩阵的 $1$ 到 $60$ 次方，这样每次询问不用重新算。

Code

#include <bits/stdc++.h>
#define MAX_N 200
#define P 998244353
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int m, p, cnt, id[10][10][10]; lnt Inv[25];
struct statas {int a, b, c;} sta[MAX_N+5];
int sum(statas s) {return s.a+s.b+s.c+1;}
struct Matrix {
    int n, ele[MAX_N][MAX_N];
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret; ret.n = n;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            lnt tmp = 0;
            for (int k = 0; k < n; k++) {
                tmp += 1LL*ele[i][k]*x.ele[k][j];
                if (tmp >= 8e18) tmp %= P;
            }
            ret.ele[i][j] = (int)(tmp%P);
        }
        return ret;
    }
} f[65];
lnt inv(lnt x) {
    if (~Inv[x]) return Inv[x];
    lnt &ret = Inv[x]; ret = 1;
    for (int k = P-2; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
Matrix mul(Matrix x, Matrix y) {
    Matrix ret; ret.n = x.n;
    for (int j = 0; j < x.n; j++) {
        lnt tmp = 0;
        for (int k = 0; k < x.n; k++) {
            tmp += 1LL*x.ele[0][k]*y.ele[k][j];
            if (tmp >= 8e18) tmp %= P;
        }
        ret.ele[0][j] = (int)(tmp%P);
    }
    return ret;
}
int main() {
    int T; read(T), read(m), read(p);
    memset(Inv, -1, sizeof Inv); Matrix mat;
    for (int i = 0; i <= p; i++)
        for (int j = 0; j <= (m <= 1 ? 0 : p-i); j++)
            for (int k = 0; k <= (m <= 2 ? 0 : p-i-j); k++)
                sta[cnt] = (statas){i, j, k}, id[i][j][k] = cnt++;
    memset(mat.ele, 0, sizeof mat.ele), mat.n = cnt+1, mat.ele[cnt][cnt] = 1;
    for (int i = 0; i < cnt; i++) mat.ele[cnt][i] = (int)inv(sum(sta[i]));
    for (int i = 0; i < cnt; i++)
        for (int j = 0; j < cnt; j++) {
            lnt x = inv(sum(sta[i]));
            if (i == j) mat.ele[i][j] = (int)x;
            else {
                if (sta[i].a) {
                    int a = sta[i].a-1, b = sta[i].b, c = sta[i].c;
                    if (a == sta[j].a && b == sta[j].b && c == sta[j].c)
                        mat.ele[j][i] = (int)(x*sta[i].a%P);
                }
                if (sta[i].b) {
                    int a = sta[i].a+1, b = sta[i].b-1, c = sta[i].c;
                    if (a+b+c < p) a += (m == 1), b += (m == 2), c += (m == 3);
                    if (a == sta[j].a && b == sta[j].b && c == sta[j].c)
                        mat.ele[j][i] = (int)(x*sta[i].b%P);
                }
                if (sta[i].c) {
                    int a = sta[i].a, b = sta[i].b+1, c = sta[i].c-1;
                    if (a+b+c < p) a += (m == 1), b += (m == 2), c += (m == 3);
                    if (a == sta[j].a && b == sta[j].b && c == sta[j].c)
                        mat.ele[j][i] = (int)(x*sta[i].c%P);
                }
            }
        }
    f[0] = mat; for (int i = 1; i <= 60; i++) f[i] = f[i-1]*f[i-1];
    while (T--) {
        lnt n; read(n);
        memset(mat.ele, 0, sizeof mat.ele), mat.ele[0][cnt] = 1;
        for (int i = 0; n && i <= 60; i++, n >>= 1)
            if (n&1) mat = mul(mat, f[i]);
        printf("%d\n", mat.ele[0][id[m==1][m==2][m==3]]);
    }
    return 0;
}