[bzoj3157]-国王奇遇记

题目（BZOJ）
 
来说说这题～
我们首先构造一个函数$$F(n,k)=\sum_{i=1}^ni^{k}m^{i}$$，然后就来推：
$$\begin{flushleft}$$
$$F(n+1,k)$$
$$=\sum_{i=1}^{n+1}i^{k}m^i$$
$$=m+\sum_{i=2}^{n+1}i^{k}m^i$$
$$=m+\sum_{i=1}^n(i+1)^{k}m^{i+1}$$
$$=m+m\sum_{i=1}^n(i+1)^km^i$$
$$=m+m\sum_{i=1}^n\sum_{j=0}^{k}C_{k}^{j}i^{j}m^{i}$$
$$=m+m\sum_{j=0}^kC_{k}^{j}\sum_{i=1}^ni^{j}m^{i}$$
$$=m+m\sum_{j=0}^kC_{k}^{j}F(n,j)$$
发现这只能一个一个推，我们来考虑倍增推:
$$F(2n,k)$$
$$=\sum_{i=1}^{2n}i^km^i$$
$$=\sum_{i=1}^ni^km^i+\sum_{i=n+1}^{2n}i^km^i$$
$$=F(n,k)+\sum_{i=1}^n(i+n)^km^{i+n}$$
$$=F(n,k)+m^n\sum_{i=1}^n\sum_{j=0}^kC_{k}^{j}i^jn^{k-j}m^i$$
$$=F(n,k)+m^n\sum_{j=0}^kC_{k}^{j}n^{k-j}\sum_{i=1}^nm^ii^j$$
$$=F(n,k)+m^n\sum_{j=0}^kC_{k}^{j}n^{k-j}F(n,j)$$
然后就可以递推or递归了，然而我写的是递归，中间需要一个二维map来记忆化一下，就可以了。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <bitset>
#include <map>
#define ll unsigned long long
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const ll mod=1e9+7;
ll m,c[250][250];
map <ll,map<ll,ll> > mp;
inline ll mi(ll a,ll b){
	ll ret=1;
	while(b){if(b&1)ret=((re
	return re
}
void init_C(){
	c[0][0]=c[1][0]=1;
	for(int i=1;i<=200;++i){
		for(int j=0;j<=i;++j){
			c[i][j]=c[i-1][j]+c[i-1][j-1];c[i][j
		}
	}
}
ll F(ll n,ll k){
	if(n==1)return mp[k][n]=m;
	if(mp[k][n])return mp[k][n];
	if(n&1){
		ll tmp1=0;
		for(int j=0;j<=k;++j)
			tmp1+=(c[k][j]*F(n-1,j)
		tmp1*=m,tmp1%=mod;
		return mp[k][n]=(m+tmp1
	}
	else{
		ll tmp2=0;
		for(int j=0;j<=k;++j)
			tmp2+=c[k][j
		tmp2*=mi(m,n/2),tmp2%=mod;
		return mp[k][n]=(F(n/2,k)+tmp2
	}
}
ll n,ans;
int main(){
	init_C();
	mp.clear();
	read(n),read(m);
	ans=F(n,m);
	printf(
	return 0;
}