bzoj3157 国王奇遇记 && bzoj 3516 国王奇遇记加强版

求∑_i(i>0&&i<=n) i^m*mⁱ mod 1000000007

令f_k=∑_i(i>0&&i<=n) i^k*mⁱ

两边同乘(m-1),整理得:(m-1)f_k=n^k*mⁿ⁺¹+∑_i(i>0&&i<=n) mⁱ*[(i-1)^k-i^k]

用二项式定理展开(i-1)^k,整理得:(m-1)f_k=n^k*mⁿ⁺¹+∑_i(i>0&&i<=n)m_i*∑_j(j>=0&&j<k)C(k,j)*(-1)^k-j*i^j

交换一下两个循环的位置,整理得(m-1)f_k=n^k*mⁿ⁺¹+∑_j(j>=0&&j<k)C(k,j)*(-1)^k-j*∑_i(i>0&&i<=n)i^j*mⁱ

好像发现了什么熟悉的东西。。。

(m-1)f_k=n^k*mⁿ⁺¹+∑_j(j>=0&&j<k)C(k,j)*(-1)^k-j*f_j

这样就能O(m²)计算了

这两题做法一模一样。。。我就贴个3157的代码吧

Portal

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN=205;
const int Mod=1e9+7;
typedef long long ll;

int n,m;

inline ll qpow(ll x,int k){
	ll ans=1;
	for(;k;x=x*x%Mod,k>>=1)
		if(k&1)ans=ans*x%Mod;
	return ans;
}

int C[MAXN][MAXN];

inline void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;++j){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
		}
	}
}

int ans,s[MAXN];

inline void Solve(){
	int inv=qpow(m-1,Mod-2);
	int nn=1,mm=qpow(m,n+1);
	s[0]=(qpow(m,n+1)-m+Mod)*inv%Mod;
	for(int i=1;i<=m;++i){
		nn=(ll)nn*n%Mod;
		s[i]=(ll)nn*mm%Mod;
		for(int j=0;j<i;++j){
			int res=(ll)C[i][i-j]*s[j]%Mod;
			if((i-j)&1)s[i]=(s[i]+Mod-res)%Mod;
			else s[i]=(s[i]+res)%Mod;
		}
		s[i]=(ll)s[i]*inv%Mod;
	}
	printf("%d\n",s[m]);
}

int main(){
	Init();
	if(m==1){
		ans=((ll)n*(n+1)>>1)%Mod;
		printf("%d\n",ans);
	}
	else Solve();
	return 0;
}

其实还有个再加强版。。。太神，不会做