目录
BZOJ 3157&3516&4126 国王奇遇记题意题解Code Of BZOJ3157Code Of BZOJ 3516
BZOJ 3157&3516&4126 国王奇遇记
题目传送门1题目传送门2题目传送门3
题意
计算\(\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\)，那么：\[ \begin{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*m\sum_{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\)。我们继续：\[ \begin{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^n\sum_{i=1}^{n}i^j*m^i \\ &= f(n,k)+m^n\sum_{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+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
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\n",f[1][m]);
return 0;
}
然而这么高端的做法过不去BZOJ3516，毕竟老年机于是我们思考更加优越的做法，我们发现上面一个做法实际上可以用一维记录，因为\(n\)只能转移到\(n+1\)或者\(2n\)，这样我们就需要思考是否可以省去\(n\)这一维。于是我们记\(f(k)=\sum_{i=1}^ni^k+m^i\) 那么：\[ \begin{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^i\sum_{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+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
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\n",((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\n",f[m]);
return 0;
}
然后。。\(O(m)\)的高端算法。。留个坑，奶一口肯定能够填回来。
转载于:https://www.cnblogs.com/Apocrypha/p/9571424.html
相关资源：JAVA上百实例源码以及开源项目
