题目描述
“A fight? Count me in!” 要打架了,算我一个。
“Everyone, get in here!” 所有人,都过来!
小Y是一个喜欢玩游戏的 OIer。一天,她正在玩一款游戏,要打一个 Boss。
虽然这个 Boss 有 $10^{100}$ 点生命值,但它只带了一个随从——一个只有 $m$ 点生命值的“恐怖的奴隶主”。
这个“恐怖的奴隶主”有一个特殊的技能:每当它被扣减生命值但没有死亡(死亡即生命值 $\leq 0$),且 Boss 的随从数量小于上限 $k$,便会召唤一个新的具有 $m$ 点生命值的“恐怖的奴隶主”。
现在小Y可以进行 $n$ 次攻击,每次攻击时,会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个,并扣减 $1$ 点生命值,她想知道进行 $n$ 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差,你的答案需要对 $998244353$ 取模。
输入格式
输入第一行包含三个正整数 $T,m,k$ 表示询问组数,$m,k$ 的含义见题目描述。
接下来 $T$ 行,每行包含一个正整数 $n$,表示询问进行 $n$ 次攻击后扣减 Boss 的生命值点数的期望。
输出格式
输出共 $T$ 行,对于每个询问输出一行一个非负整数,表示该询问的答案对 $998244353$ 取模的结果。
可以证明,所求期望一定是一个有理数,设其为$p/q (\mathrm{gcd}(p,q) = 1)$ 那么你输出的数 $x$ 要满足 $p \equiv qx \mod 998244353$。
样例
输入
输出
1 2 3
| 499122177 415935148 471393168
|
数据范围与提示
在所有测试点中, $1\leq T \leq 1000, 1 \leq n \leq 10^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8$
各个测试点的分值和数据范围如下:
测试点编号 | 分值 | $T=$ | $n \leq $ | $m=$ | $k=$ |
---|
1 | 3 | 10 | 10 | 1 | 1 |
2 | 8 | 2 | 8 |
3 | 7 | $10^{18}$ | 3 |
4 | 12 | 7 |
5 | 30 | 20 | 3 | 5 |
6 | 10 | 500 | 6 |
7 | 10 | 200 | 7 |
8 | 5 | 1000 |
9 | 10 | 100 | 8 |
10 | 5 | 500 |
题解
20pts
可以直接$DP$
同[BZOJ 4832] [Lydsy2017年4月月赛]抵制克苏恩
100pts
发现每次转移都是一样的
然后就可以矩阵快速幂了。
然而并不能过 2333
时间复杂度为$O(Tcnt^3log(n))$, $cnt$不会超过200。
我们还需要优化
我们可以将转移矩阵的 $k$ 次方全部预处理出来, 然后用一个 $1 \times cnt$ 的矩阵不断的去乘, 这样时间复杂度会被降到 $O(cnt^3log(n) + Tcnt^2log(n))$
就可以过了。
好像是道水题
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 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
| #include <cstdio> #include <cstring> #include <algorithm> using namespace std; inline long long read() { long long x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MOD = 998244353; struct Matrix { int a[200][200]; int n, m; Matrix(int _n = 0, int _m = 0) { n = _n, m = _m; memset (a, 0, sizeof (a)); } Matrix operator * (const Matrix &b) const { Matrix ans(n, b.m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int k = 1; k <= b.m; k++) ans.a[i][k] = (ans.a[i][k] + 1ll * a[i][j] * b.a[j][k]) % MOD; return ans; } }A[64]; long long pow_mod(long long a, int b) { long long ans = 1; while (b) { if (b & 1) ans = ans * a % MOD; b >>= 1; a = a * a % MOD; } return ans; } int cnt[10][10][10], Index, IDans; int main() { int T = read(), m = read(), k = read(); for (int i = 0; i <= k; i++) for (int j = 0; j <= (m == 1 ? 0 : k); j++) for (int l = 0; l <= ((m == 1 || m == 2) ? 0 : k); l++) if (i + j + l <= k) cnt[i][j][l] = ++Index; IDans = ++Index; if (m == 1) { for (int i = 0; i <= k; i++) { if (i > 0) (A[0].a[cnt[i][0][0]][cnt[i - 1][0][0]] += i * pow_mod(i + 1, MOD - 2) % MOD) %= MOD; (A[0].a[cnt[i][0][0]][cnt[i][0][0]] += pow_mod(i + 1, MOD - 2)) %= MOD; (A[0].a[cnt[i][0][0]][IDans] += pow_mod(i + 1, MOD - 2)) %= MOD; } A[0].a[IDans][IDans] = 1; } else if (m == 2) { for (int j = 0; j <= k; j++) for (int l = 0; l <= k; l++) if (l + j <= k) { if (l >= 1 && j + l + 1 <= k) (A[0].a[cnt[j][l][0]][cnt[j + 1][l][0]] += pow_mod(j + l + 1, MOD - 2) * l % MOD) %= MOD; if (l >= 1 && j + l + 1 > k) (A[0].a[cnt[j][l][0]][cnt[j + 1][l - 1][0]] += pow_mod(j + l + 1, MOD - 2) * l % MOD) %= MOD; if (j >= 1) (A[0].a[cnt[j][l][0]][cnt[j - 1][l][0]] += pow_mod(j + l + 1, MOD - 2) * j % MOD) %= MOD; (A[0].a[cnt[j][l][0]][cnt[j][l][0]] += pow_mod(j + l + 1, MOD - 2)) %= MOD; (A[0].a[cnt[j][l][0]][IDans] += pow_mod(j + l + 1, MOD - 2)) %= MOD; } A[0].a[IDans][IDans] = 1; } else { for (int i = 0; i <= k; i++) for (int j = 0; j <= k; j++) for (int l = 0; l <= k; l++) if (i + j + l <= k) { if (i > 0) (A[0].a[cnt[i][j][l]][cnt[i - 1][j][l]] += i * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD; if (j > 0) { if (i + j + l + 1 <= k) (A[0].a[cnt[i][j][l]][cnt[i + 1][j - 1][l + 1]] += j * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD; else (A[0].a[cnt[i][j][l]][cnt[i + 1][j - 1][l]] += j * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD; } if (l > 0) { if (i + j + l + 1 <= k) (A[0].a[cnt[i][j][l]][cnt[i][j + 1][l]] += l * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD; else (A[0].a[cnt[i][j][l]][cnt[i][j + 1][l - 1]] += l * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD; } (A[0].a[cnt[i][j][l]][cnt[i][j][l]] += pow_mod(i + j + l + 1, MOD - 2)) %= MOD; (A[0].a[cnt[i][j][l]][IDans] += pow_mod(i + j + l + 1, MOD - 2)) %= MOD; } A[0].a[IDans][IDans] = 1; } A[0].n = A[0].m = Index; for (int i = 1; i <= 63; i++) A[i] = A[i - 1] * A[i - 1]; while (T--) { Matrix B(1, Index); B.a[1][cnt[m == 1][m == 2][m == 3]] = 1; long long n = read(); for (int i = 0; i <= 63; i++) if (n & (1ll << i)) B = B * A[i]; printf ("%d\n", B.a[1][IDans]); } }
|