博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ5339:[TJOI2018]教科书般的亵渎——题解
阅读量:7077 次
发布时间:2019-06-28

本文共 1352 字,大约阅读时间需要 4 分钟。

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

参考: ,你可以在这个博客里面找到各种各样的本题做法。

题意很乱,但是整理整理后发现实际上你只需要知道如何求出\(S(n,k)=\sum_{i=1}^na_i^k\)即可。

直接给公式\(S(n,k)=\frac{1}{k+1}\sum_{i=1}^{k+1}C^i_{k+1}B_{k+1-i}(n+1)^i\)

组合数递推:

\(C^m_n=C^m_{n-1}+C^{m-1}_{n-1}\)

伯努利数递推:

\(B_n=[m=0]-\sum_{k=0}^{m-1}C_m^k\frac{B_k}{m-k+1}\)

\(m=n-1\)

#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;const ll p=1e9+7;const int N=65;inline ll read(){ ll X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}ll n,a[N],inv[N],c[N][N],b[N];int m;ll qpow(ll x,ll y){ ll res=1; while(y){ if(y&1)res=res*x%p; x=x*x%p;y>>=1; } return res;}ll f(ll x,ll y){ ll res=0; for(int i=1;i<=y+1;i++){ res=(res+c[y+1][i]*b[y+1-i]%p*qpow(x+1,i)%p)%p; } res=res*inv[y+1]%p; return res;}inline void init(){ for(int i=1;i

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客: +

+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/9066431.html

你可能感兴趣的文章
iOS模拟器,点击textfield为什么不弹出软键盘
查看>>
Jetty 7.6.8 和 8.1.8 发布
查看>>
程序员如何做出“不难看”的设计
查看>>
类苹果启动器 Cairo Dock 3.1.2 稳定版发布
查看>>
2012用户体验年会 奇虎360CEO兼首席体验官 周鸿祎主题演讲——简而未减
查看>>
Shipping your PyQt app for windows
查看>>
keil MDK编译器警告和错误详解
查看>>
javascript/jquery判断是否为undefined或是null!
查看>>
hdu3791(二叉搜索树)
查看>>
[C#]解决生成的缩略图模糊的问题
查看>>
jQuery常用标签详解
查看>>
学用MVC4做网站五:文章
查看>>
学习C++ -> 引用( References )
查看>>
分享:在Qt工程中加Boost
查看>>
远程桌面相关
查看>>
减少Linux 电耗 转自IBM
查看>>
新的一年又开始了,加油2013!
查看>>
Sharepoint学习笔记—习题系列--70-573习题解析 -(Q22-Q24)
查看>>
ios block循环引用问题
查看>>
地图覆盖物
查看>>