题面：BZOJ3157
一句话题意：
求：
\[\sum_{i=1}^ni^m\ \times m^i\ (mod\ 1e9+7)\ \ (n \leq 1e9,m\leq200)
\]
\]
题解
令
\[DP[i]=\sum_{k=1}^n k^i*m^k
\]
\]
则
\[(m-1)DP[i]=mDP[i]-DP[i]
\]
\]
\[=\sum_{k=1}^{n}k^im^{k+1}-\sum_{k=1}^nk^im^k
\]
\]
\[=\sum_{k=2}^{n+1}(k-1)^im^k-\sum_{k=1}^nk^im^k
\]
\]
\[=n^n m^{n+1}+\sum_{k=1}^nm^k*((k-1)^i-k^i)
\]
\]
由二项式反演得
\[=n^im^{n+1}+\sum_{k=1}^n \sum_{j=1}^{i-1}(-1)^{i-j}*C_i^j\ k^jm^k
\]
\]
\[=n^im^{n+1}+\sum_{j=0}^{i-1}(-1)^{i-j}*C_i^j\times DP[j]
\]
\]
于是就可以\(O(m^2log(mod))\)递推了！
#include<bits/stdc++.h>
using namespace std;
namespace Tzh{
typedef long long ll;
const int maxm=210;
const ll p=1e9+7;
ll n,m,dp[maxm],c[maxm][maxm];
ll qpow(ll a,ll b){
ll sum=1;
while(b){
if(b&1) sum=sum*a%p;
a=a*a%p; b>>=1;
}
return sum;
}
void init(){c[0][0]=1;
for(int i=1;i<=m;i++){c[i][0]=1;
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
}
}
void work(){
scanf("%lld%lld",&n,&m); init();
if(m==1){
printf("%lld",(n+1)*n/2%p);
return ;
}
dp[0]=(qpow(m,n+1)-m+p)%p*qpow(m-1,p-2)%p;
for(int i=1;i<=m;i++){
dp[i]=qpow(n,i)*qpow(m,n+1)%p;
for(int j=0;j<i;j++)
dp[i]=(dp[i]+p+((i-j)&1?-1:1)*c[i][j]*dp[j]%p)%p;
dp[i]=dp[i]*qpow(m-1,p-2)%p;
}
printf("%lld",dp[m]);
return ;
}
}
int main(){
Tzh::work();
return 0;
}