PDF《IOI 2018 中国国家集训队集中培训》

'

恐怖的奴隶主'

'

. 这个 '

'

恐怖的奴隶主'

'

有一个特殊的技能:每当它被扣减生命值但没有死亡(死亡 即生命值 ≤ 0) ,且Boss 的随从数量小于上限 k,便会召唤一个新的具有 m 点生命值的 '

'

恐怖的奴隶主'

'

. 现在小 Y 可以进行 n 次攻击,每次攻击时,会从 Boss 以及 Boss 的所有随从中的 等概率随机选择一个,并扣减

1 点生命值,她想知道进行 n 次攻击后扣减 Boss 的生命 值点数的期望.为了避免精度误差,你的答案需要对

998244353 取模. 【输入格式】 从文件 patron.in 中读入数据. 输入第一行包含三个正整数 T, m, k,T 表示询问组数,m, k 的含义见题目描述. 接下来 T 行,每行包含一个正整数 n,表示询问进行 n 次攻击后扣减 Boss 的生命 值点数的期望. 【输出格式】 输出到文件 patron.out 中. 输出共 T 行, 对于每个询问输出一行一个非负整数, 表示该询问的答案对

998244353 取模的结果. 可以证明,所求期望一定是一个有理数,设其为 p/q(gcd(p, q) = 1) ,那么你输出 的数 x 要满足 p ≡ qx (mod 998244353). 【样例

1 输入】

3 2

6 1

2 3 第8页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和恐怖的奴隶主(patron) 【样例

1 输出】

499122177 415935148

471393168 【样例

1 解释】 对于第一次询问,第一次攻击有

1 2 的概率扣减 Boss 的生命值,有12的概率扣减随 从的生命值,所以答案为

1 2 .1 ≡

2 ?

499122177 (mod 998244353). 对于第二次询问,如果第一次攻击扣减了 Boss 的生命值,那么有

1 2 的概率第二 次攻击仍扣减 Boss 的生命值,有12的概率第二次攻击扣减随从的生命值;

如果第一 次攻击扣减了随从的生命值,那么现在又新召唤了一个随从('

'

恐怖的奴隶主'

'

) ,于 是有

1 3 的概率第二次攻击扣减 Boss 的生命值,有23的概率第二次攻击扣减随从的生 命值.所以答案为

1 2 ?

1 2 ?

2 +

1 2 ?

1 2 ?

1 +

1 2 ?

1 3 ?

1 +

1 2 ?

2 3 ?

0 =

11 12 .11 ≡

12 ?

415935148 (mod 998244353). 【样例 2】 见选手目录下的 patron/patron2.in 与patron/patron2.ans. 该组样例的数据范围(除询问组数 T 外)同第

7、8 个测试点. 【提示】 题目顺序可能与难度无关. 【子任务】 在所有测试点中,1 ≤ T ≤ 1000,

1 ≤ n ≤

1018 ,

1 ≤ m ≤ 3,

1 ≤ k ≤ 8. 各个测试点的分值和数据范围如下: 第9页共10 页IOI

2018 中国国家集训队集中培训 第二试 小Y和恐怖的奴隶主(patron) 测试点编号 分值 T = n ≤ m = k =

1 3

10 10

1 1

2 8

2 8

3 7

1018 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 第10 页共10 页 ........