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

发表于
字数统计: 1,506 | 阅读时长 ≈ 7

Problem

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

时间限制：
内存限制：

题目描述

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

输入格式

输入第一行包含三个正整数 ， 表示询问组数， 的含义见题目描述。
接下来 行，每行包含一个正整数 ，表示询问进行 次攻击后扣减 的生命值点数的期望。

输出格式

输出共 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 取模的结果。
可以证明，所求期望一定是一个有理数，设其为 （ ），那么你输出的数 要满足 。

样例

输入

1
2
3
4
3 2 6
1
2
3

输出

1
2
3
499122177
415935148
471393168

解释
对于第一次询问，第一次攻击有 的概率扣减 的生命值，有 的概率扣减随从的生命值，所以答案为 。 。
对于第二次询问，如果第一次攻击扣减了 的生命值，那么有 的概率第二次攻击仍扣减 的生命值，有 的概率第二次攻击扣减随从的生命值；如果第一次攻击扣减了随从的生命值，那么现在又新召唤了一个随从（“恐怖的奴隶主”），于是有 的概率第二次攻击扣减 的生命值，有 的概率第二次攻击扣减随从的生命值。所以答案为 。 。

数据范围与提示

在所有测试点中， , , ,
各个测试点的分值和数据范围如下：

测试点编号 分值

标签：概率DP 矩阵快速幂

Solution

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

考虑如何构造转移矩阵。转移矩阵相当于记录一个状态转移成另一个状态的概率。记状态 表示血量为 的奴隶主各有 个的状态，则和弱化版相同，枚举打哪种奴隶主进行转移即可。然而有一种情况无法转移，即打脸的情况（对应 ）。我们只需要给转移矩阵多开一行，存储 即可。对应地，答案矩阵也需要多开一行，开始时这一行的数为 。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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;
}
------------- Thanks For Reading -------------
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多
0%