LuoguP4593 [TJOI2018]教科书般的亵渎

Description

题目链接

小豆喜欢玩游戏,现在他在玩一个游戏遇到这样的场面,每个怪的血量为 $a_i$,且每个怪物血量均不相同,小豆手里有无限张“亵渎”。亵渎的效果是对所有的怪造成 $1$ 点伤害,如果有怪死亡,则再次施放该法术。我们认为血量为 $0$ 怪物死亡。

小豆使用一张 “亵渎”会获得一定的分数,分数计算如下,在使用一张“亵渎”之后,每一个被亵渎造成伤害的怪会产生 $x^k$,其中 $x$ 是造成伤害前怪的血量为 $x$ 和需要杀死所有怪物所需的“亵渎”的张数 $k$。

$1\leq n \leq 10^{13},1\leq m \leq 50$。

Solution

对于一段 $[1,m]$ 的怪,显然只需要一次亵渎即可杀死所有怪物,所以我们总共需要 $k=m+1$ 次亵渎即可杀死所有怪。

那么,只需要把怪看成一段一段的,并且用总贡献减去空的贡献即可。

$$Ans=\sum_{i=0}^m(\sum_{j=1}^{n-a_i}j^k-\sum_{j=i+1}^{m}(a_i-a_j)^k)$$

直接套拉格朗日插值板子即可。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇