Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 5339: [TJOI2018]教科书般的亵渎

题目链接

传送门

Description

小豆喜欢玩游戏, 现在他在玩一个游戏遇到这样的场面,每个怪的血量为ai,且每个怪物血量均不相同, 小豆手里有无限张“亵渎”。亵渎的效果是对所有的怪造成1点伤害,如果有怪死亡,则再次施放该法术。我们认为血量为0怪物死亡。小豆使用一张“亵渎”会获得一定的分数,分数计算如下,在使用一张“亵渎”之后,每一个被亵渎造成伤害的怪会产生x^k,其中x是造成伤害前怪的血量为x和需要杀死所有怪物所需的“亵渎”的张数k。

Input

第一行输入一个T,表示有多少组测试数据。
每组组测试数据第一行为n,m,表示有当前怪物最高的血量n,和m种没有出现的血量。
接下来m行,每行1个数ai,表示场上没有血量为ai的怪物。
T ≤10 n ≤ 10^13 m ≤ 50

Output

一共T行,每行一个数,
第i行表示第i组测试数据中小豆的最后可以获得的分数
因为这个分数会很大,需要模10^9 + 7。

Sample Input

2

10 1

5

4 2

1

2

Sample Output

415

135

想说的话

这个游戏玩的嘛。。。很像炉石传说嘛

题解

考虑到这个题太难算了 找找看这个题求的是什么

然后有了一种好玩的数
Bernoulli数提供给我们一种方法求出上面的式子

然后发现好多东西我们都可以预处理
比如说组合数的递推公式

再比如说后面的幂运算我们可以用逆元相对求出
剩下的就是Bernoulli数
这个数公式也有

现在就可以算这个东西了
你把没有存在的东西拿掉 然后就轻松了

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏