题意
求(sum_{k=1}^{n}k^mm^k (nleq1e9,mleq1e3))
思路
在<<具体数学>>中有一个方法用来求和，称为摄动法。
我们考虑用摄动法来求这个和式，看能不能得到比较好的复杂度。
首先令(f(i)=sum_{k=1}^nk^im^{k})。
然后开始表演[egin{align*} (m-1)f(i)&=sum_{k=1}^nk^im^{k+1}-sum_{k=1}^nk^im^k \ &=sum_{k=1}^{n+1}(k-1)^im^k-sum_{k=1}^nk^im^k\ &=n^im^{n+1}+sum_{k=1}^nm^ksum_{j=0}^{i-1}C_i^j(-1)^{i-j}k^j\ &=n^im^{n+1}+sum_{j=0}^{i-1}C_i^j(-1)^{i-j}sum_{k=1}^nk^jm^k\ &=n^im^{n+1}+sum_{j=0}^{i-1}C_i^j(-1)^{i-j}f(j) end{align*} ]
于是我们很神奇的得到了一个(O(m^2))的递推式。
对于解决此题已经足够了。
另外对于这个和式有多项式插值法可以(O(m))解决。
具体例题bzoj4126。
代码
# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1e16
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline char nc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int Scan(){
char ch=nc();int sum=0, f=1;
if (ch=='-') f=-1, ch=nc();
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum*f;
}
const int N=1005;
//Code begin....
LL C[N][N], ANS[N], INV, COM, P;
LL pow_mod(LL a, LL n, LL mod){
LL ret=1, tmp=a%mod;
while (n) {
if (n&1) ret=ret*tmp%MOD;
tmp=tmp*tmp%MOD;
n>>=1;
}
return ret;
}
LL inv(LL a, LL mod){return pow_mod(a,mod-2,mod);}
void init(){
FOR(i,0,1000) {
C[i][0]=C[i][i]=1;
FOR(j,1,i-1) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
}
}
int main ()
{
int n, m;
init();
scanf("%d%d",&n,&m);
if (m==1) {printf("%lld
",(LL)n*(n+1)/2%MOD); return 0;}
INV=inv(m-1,MOD); COM=pow_mod(m,n+1,MOD);
ANS[0]=(COM-m)*INV%MOD; P=1;
if (ANS[0]<0) ANS[0]+=MOD;
FOR(i,1,m) {
P=P*n%MOD;
LL sum=P*COM%MOD;
FOR(j,0,i-1) {
if ((i+j)&1) sum-=C[i][j]*ANS[j]%MOD;
else sum+=C[i][j]*ANS[j]%MOD;
}
sum%=MOD;
if (sum<0) sum+=MOD;
ANS[i]=sum*INV%MOD;
}
printf("%lld
",ANS[m]);
return 0;
}