扰动法--*BZOJ3157: 国王奇遇记
求$\sum_{i=1}^ni^mm^i$。$n \leq 1e9,m \leq 200$。
其实我也不知道这东西为啥叫“扰动法”,大概是在黑暗的边缘试探?就是那种,人家再多一点就被您看破了,然后您就一定要搞他那么一点去试探他的限度,一不小心给他搞爆了,这种感觉。
扰动三连:
等比数列求和:
$\sum_{i=1}^na_i,a_i=a_1*q^{n-1}$。
令$S_n=\sum_{i=1}^na_i$。
给他日上个$n+1$。
$S_n+a_{n+1}$
$=\sum_{i=1}^{n+1}a_i$
$=a_1+q\sum_{i=1}^na_i$
$=a_1+qS_n$
可得$S_n=\frac{a_1(1-q^n)}{1-q}$,厉害吧!
自然数幂求和:
$\sum_{i=1}^ni^m$。
令$S_n^m=\sum_{i=1}^ni^m$。
给他日上个$n+1$。
$S_n^m+(n+1)^m$
$=\sum_{i=1}^{n+1}i^m$
$=1+\sum_{i=1}^n(i+1)^m$
$=1+\sum_{i=1}^n\sum_{j=0}^m\binom{m}{j}i^j$
$=1+\sum_{j=0}^m\binom{m}{j}\sum_{i=1}^ni^j$
$=1+\sum_{j=0}^{m-1}\binom{m}{j}S_n^j+S_n^m$
emmmmmm自己把自己日掉了,不虚我们把$m$变成$m+1$。
$S_n^{m+1}+(n+1)^{m+1}$
$=1+\sum_{j=0}^{m}\binom{m+1}{j}S_n^j+S_n^{m+1}$
$=1+\sum_{j=0}^{m-1}\binom{m+1}{j}S_n^j+S_n^{m+1}+(m+1)S_n^m$
已经知道了。$S_n^m=\frac{(n+1)^{m+1}-\sum_{j=0}^{m-1}\binom{m+1}{j}S_n^j}{m+1}$。
可以$m^2$。要是给个好膜数可以$mlogm$。
这道题:
令$S_n^m=\sum_{i=1}^ni^mm^i$。
给他日上个$n+1$。
$S_n^m+(n+1)^mm^{n+1}\\$
$=\sum_{i=1}^{n+1}i^mm^i\\$
$=m+\sum_{i=2}^{n+1}i^mm^i\\$
$=m+m\sum_{i=1}^{n}(i+1)^mm^i\\$
$=m+m\sum_{i=1}^{n}m^i\sum_{j=0}^m\binom{m}{j}i^j\\$
$=m+m\sum_{j=0}^{m}\binom{m}{j}\sum_{i=1}^nm^ii^j\\$
$=m+m\sum_{j=0}^{m-1}\binom{m}{j}\sum_{i=1}^nm^ii^j+mS_n^m$
emmmmmm为什么这里也要emmmmmm,因为化出来那个$\sum_{i=1}^nm^ii^j$跟咱想象的不太一样,那咱换个字母重来一遍。
令$S_n^k=\sum_{i=1}^ni^km^i$。
如此$S_n^k+(n+1)^km^{n+1}=...=m+m\sum_{j=0}^{k-1}\binom{k}{j}S_n^j+mS_n^k$。
搞定了。$m^2$解决。模数优秀可以$mlogm$。
最新文章
- MonogDB初探增加和删除
- Java语法
- SSD果然劲爆!
- <;<;卸甲笔记>;>;-Oracle线下迁移到PPAS
- JAVA定义接口格式:
- SSIS ->;>; Script Task
- BS软件注册
- Android 应用启动渐变效果
- redis基本命令的演示:
- PHP zip压缩文件及解压
- hdu4496 D-City
- MacOS和iOS开发中异步调用与多线程的区别
- eclipse使用Git基本流程
- 一、Swagger配置
- java 中的强制转换
- js选择排序。
- Java四类八种数据类型
- 23种设计模式之原型模式(Prototype)
- 用R画韦恩图
- 验证手机格式的js代码