bzoj 3157: 国王奇遇记3516: 国王奇遇记加强版

题意

给定$n,m$
计算${\sum }_{i=1}^n{i}^m?m^i$
$n\le 10^9,m\le 5000$

题解

很玄妙的题，看起来完全不会做，实际上也完全不会做
考虑递推！
$n$很大，因此递推只可以和$m$有关
和$m$有关系的有两个，一个是指数上的，一个是底数上的
那么有三种情况，递推其中一个，或者两个一起
根据题解，我们考虑递推指数上的
那么设计状态$f_i={\sum }_{j=0}^n{j}^i?m^j$
可以发现，$f_0$就是等比数列求和，可以直接求出来，那么第一项就有了
那么问题在于转移，考虑用类似等比数列求和的方法来求和
也就是两边同时乘$m$，然后做差
$m{f}_i={\sum }_{j=0}^n{j}^i?m^{j+1}$
$$(m?1)f_i=\sum _{j=0}^n{j}^i?m^{j+1}?\sum _{j=0}^n{j}^i?m^j$$
$$=m^{n+1}{n}^m+\sum _{j=1}^n(j?1{)}^i?m^j?\sum _{j=1}^n{j}^i?m^j$$
$$=m^{n+1}{n}^m+\sum _{j=1}^n{m}^j((j?1{)}^i?j^i)$$
$$=m^{n+1}{n}^m+\sum _{j=1}^n{m}^j(\sum _{k=0}^{i?1}{j}^k{C}_i^k(?1{)}^{i?k})$$
套路地转化主体
$$=m^{n+1}{n}^m+\sum _{k=0}^{i?1}{C}_i^k(?1{)}^{i?k}\sum _{j=1}^n{m}^j{j}^k$$
可以发现，后面这个东西，不就是$f$的定义吗？
$$=m^{n+1}{n}^m+\sum _{k=0}^{i?1}{C}_i^k(?1{)}^{i?k}{f}_j$$

然后就得到了一个玄妙的$O(m^2)$的做法

以后这种题，不妨试试递推的方式，然后通过类似等比数列求和的套路，同乘$m$，尽量和之前的状态扯上关系，来得到可以递推的效果

em…听说还有$O(m)$的做法，以后再来填吧

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=255;
const int MOD=1e9+7;
int add (int x,int y)   {
    x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y)   {
    return (LL)x*y%MOD;}
int dec (int x,int y)   {
    x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
    if (y==1) return x;int lalal=Pow(x,y>>1);lalal=mul(lalal,lalal);if (y&1) lalal=mul(lalal,x);return lalal;
}
int n,m;
int C[N][N];
int f[N];
int main()
{
    scanf("%d%d",&n,&m);if (m==1){
    printf("%d\n",((LL)n*(n+1)/2)%MOD);return 0;}C[0][0]=1;for (int u=1;u<=m;u++){
    C[u][0]=1;for (int i=1;i<=u;i++)   C[u][i]=add(C[u-1][i-1],C[u-1][i]);}f[0]=mul(mul(m,dec(1,Pow(m,n))),Pow(dec(1,m),MOD-2));int lalal=Pow(m,n+1),inv=Pow(m-1,MOD-2);for (int u=1;u<=m;u++){
    lalal=mul(lalal,n);int cnt=0;for (int j=0;j<u;j++){
    int now=mul(C[u][j],f[j]);if ((u-j)&1) cnt=dec(cnt,now);else cnt=add(cnt,now);}f[u]=mul(inv,add(lalal,cnt));}printf("%d\n",f[m]);return 0;
}