BZOJ 3157&3516&4126 国王奇遇记
题意
计算(sum_{i=1}^{n}i^m*m^i) (\%) (10^9+7)
((1 leq n leq 10^9))
BZOJ3157:(1 leq m leq 200)
BZOJ3516:(1 leq m leq 1000)
BZOJ4126:(1 leq m leq 50000)
题解
一般题目短的都很毒这道题各种做法都有，想不想的出来似乎只有看推式子的能力了。推不出式子的话那就只能乱搞了。先讲一种自己单独想出来的但是复杂度爆炸的做法，复杂度似乎是(O(m^3log(n)))的，然而似乎可以过。。首先我们把这个式子用拆成这样：(sum_{i=1}^{n}i^m*m^i=m*(1^m+m(2^m+m(...m(n^m)))))，然后可以发现这个式子是非常有规律的，于是我们就考虑矩乘，但这个(i^m)非常的难弄，所以我们在矩阵中同时记录这个(i^m)，然后一起转移就行了，然而这个看起来非常好写的做法复杂度很高，然而代码也调了好久（感觉自己蒿菜啊～），所以代码就不放了2333。
然后开始讲一下比较高端的做法。。首先是(O(m^2log(n)))的做法，我们记(f(n,k)=sum_{i=1}^{n}i^k*m^i)，那么：
[egin{array}
& f(n+1,k) &= sum_{i=1}^{n+1}i^k*m^i \
&=sum_{i=2}^{n+1}i^k*m^i+m \
&=sum_{i=1}^{n}(i+1)^k*m^{i+1}+m \
&=sum_{i=1}^{n}m^{i+1}sum_{j=0}^kC_k^j*i^j+m \
&=sum_{j=0}^{k}C_k^j*msum_{i=1}^ni^j*m^i+m \
&=sum_{j=0}^kC_k^j*m*f(n,j)+m
end{array}
]
这样我们就可以用(O(m^2))的时间从(n)转移到(n+1)。我们继续：
[egin{array}
& f(2n,k) &= sum_{i=1}^{2n}i^k*m^i \
&= sum_{i=1}^{n}i^k*m^i+sum_{i=n+1}^{2n}i^k*m^i \
&= f(n,k)+sum_{i=1}^{n}(i+n)^k*m^{i+n} \
&= f(n,k)+sum_{i=1}^{n}m^{i+n}sum_{j=0}^{k}C_k^j*i^j*n^{k-j} \
&= f(n,k)+sum_{j=0}^{k}C_k^j*n^{k-j}*m^nsum_{i=1}^{n}i^j*m^i \
&= f(n,k)+m^nsum_{j=0}^{k}C_k^j*n^{k-j}*f(n,j)
end{array}
]
这样我们就可以同样用(O(m^2))的时间从(n)转移到(2n)。接下来就是比较简单的递归处理了，总复杂度为(O(m^2log(n)))。
Code Of BZOJ3157
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int Md=1e9+7;
const int N=205;
ll n;
int m;
ll C[N][N],f[N][N];
/*==================Define Area================*/
ll Powe(ll x,ll y) {
ll res=1;
while(y) {
if(y&1) res=1ll*res*x%Md;
x=1ll*x*x%Md;
y>>=1;
}
return res;
}
void Init() {
C[0][0]=1;
for(int i=1;i<=m;i++) {
C[i][0]=1;
for(int j=1;j<=m;j++) {
C[i][j]=(C[i-1][j]+C[i-1][j-1])%Md;
}
}
}
void Calc(ll x,int y) {
if(x==1) {
for(int i=0;i<=m;i++) {
f[y][i]=m;
}
return ;
}
if(x&1) {
Calc(x-1,y+1);
for(int i=0;i<=m;i++) {
for(int j=0;j<=i;j++) {
(f[y][i]+=(f[y+1][j]*C[i][j])%Md)%=Md;
}
(f[y][i]*=m)%=Md;(f[y][i]+=m)%=Md;
}
}
else {
Calc(x/=2,y+1);ll Pw=Powe(m,x);
for(int i=0;i<=m;i++) {
for(int j=0;j<=i;j++) {
(f[y][i]+=(C[i][j]*Powe(x,i-j)%Md*f[y+1][j])%Md)%=Md;
}
(f[y][i]*=Pw)%=Md;
(f[y][i]+=f[y+1][i])%=Md;
}
}
}
int main() {
read(n);read(m);
Init();
Calc(n,1);
printf("%lld
",f[1][m]);
return 0;
}
然而这么高端的做法过不去BZOJ3516，毕竟老年机于是我们思考更加优越的做法，我们发现上面一个做法实际上可以用一维记录，因为(n)只能转移到(n+1)或者(2n)，这样我们就需要思考是否可以省去(n)这一维。于是我们记(f(k)=sum_{i=1}^ni^k+m^i)
那么：
[egin{array}
& (m-1)*f(k) &= (m-1)*sum_{i=1}^{n}i^k*m^i \
&= sum_{i=1}^ni^k*m^{i+1} -sum_{i=1}^ni^k*m^i \
&= sum_{i=2}^{n+1}(i-1)^k*m^i-sum_{i=1}^ni^k*m^i \
&= sum_{i=1}^{n}((i-1)^k-i^k)*m^i+n^km^{n+1} \
&= sum_{i=1}^{n}m^isum_{j=0}^{k-1}C_k^j*(-1)^{k-j}*i^j+n^km^{n+1} \
&= sum_{j=0}^{k-1}C_k^j*(-1)^{k-j}*sum_{i=1}^{n}i^j*m^i+n^km^{n+1} \
&= sum_{j=0}^{k-1}C_k^j*(-1)^{k-j}*f(j)+n^km^{n+1}
end{array}
]
于是我们可以得出(f(k)=frac{sum_{j=0}^{k-1}C_k^j*(-1)^{k-j}*f(j)+n^km^{n+1}}{m-1})。这样我们就得到了(O(m^2))的做法，就可以过BZOJ3516的数据范围了。
Code Of BZOJ 3516
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const ll Md=1e9+7;
const int N=2005;
int n,m;
ll C[N][N],f[N];
/*==================Define Area================*/
void Init() {
C[0][0]=1;
for(int i=1;i<=m;i++) {
C[i][1]=i;C[i][0]=1;
for(int j=2;j<=i;j++) {
C[i][j]=(C[i-1][j]+C[i-1][j-1])%Md;
}
}
}
ll Powe(ll x,int y) {
ll res=1;
while(y) {
if(y&1) res*=x,res%=Md;
x*=x;x%=Md;
y>>=1;
}
return res;
}
int main() {
read(n);read(m);
Init();
if(m==1) return printf("%lld
",((ll)(n+1)*n/2)%Md),0;
ll Sum=Powe(m,n+1);
f[0]=(Sum-m+Md)%Md;
ll Div=Powe(m-1,Md-2);f[0]*=Div;f[0]%=Md;
for(int i=1;i<=m;i++) {
Sum*=n;Sum%=Md;f[i]=Sum;
for(int j=0;j<i;j++) {
int F=((i-j)&1)?-1:1;
(f[i]+=C[i][j]*F*f[j]%Md)%=Md;
}
(f[i]+=Md)%=Md;
f[i]*=Div;f[i]%=Md;
}
printf("%lld
",f[m]);
return 0;
}
然后。。(O(m))的高端算法。。留个坑，奶一口肯定能够填回来。