【BZOJ】【3157】&【BZOJ】【3516】国王奇遇记

数论

---

　　题解：http://www.cnblogs.com/zhuohan123/p/3726933.html

　　copy一下推导过程：

令$$S_i=\sum_{k=1}^{n}k^im^k$$

我们有$$ \begin{aligned} (m-1)S_i &= mS_i-S_i \\&=\sum_{k=1}^n k^im^{k+1}-\sum_{k=1}^n k^i m^k \\&=\sum_{k=2}^{n+1}(k-1)^i m^k-\sum_{k=1}^n k^i m^k \\&=n^i m^{n+1}+\sum_{k=1}^n m^k ( (k-1)^i-k^i ) \\&=n^i m^{n+1}+\sum_{k=1}^n \big( \sum_{j=1}^{i-1}(-1)^{i-j} \binom{i}{j}k^jm^k\big) \\&=n^i m^{n+1}+\sum_{j=0}^{i-1}(-1)^{i-j}\binom{i}{j} S_j \end{aligned} $$

 /**************************************************************

     Problem: 3516

     User: Tunix

     Language: C++

     Result: Accepted

     Time:372 ms

     Memory:1300 kb

 ****************************************************************/

 //BZOJ 3157

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 typedef long long LL;

 const int N=;

 const LL P=;

 /*******************template********************/

 #define sqr(x) (x)*(x)

 LL n,m;

 LL fac[N],inv[N],s[N];

 LL C(int a,int b){return fac[a]*inv[b]%P*inv[a-b]%P;}

 LL Pow(LL a,LL b){

     LL r=;

     for(;b;b>>=,a=a*a%P) if (b&) r=r*a%P;

     return r;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("3157.in","r",stdin);

     freopen("3157.out","w",stdout);

 #endif

     scanf("%lld%lld",&n,&m);

     if (m==){ printf("%lld\n",(n+)*n/%P);return ;}

     fac[]=; F(i,,m) fac[i]=fac[i-]*i%P;

     inv[m]=Pow(fac[m],P-);

     inv[]=;

     D(i,m-,) inv[i]=inv[i+]*(i+)%P;

     s[]=((Pow(m,n+)-m)%P+P)%P*Pow(m-,P-)%P;

     F(i,,m){

         s[i]=Pow(n,i)*Pow(m,n+)%P;

         rep(j,i) s[i]=((s[i]+((i-j)%== ? - : )*C(i,j)*s[j])%P+P)%P;

         s[i]=s[i]*Pow(m-,P-)%P;

     }

     printf("%lld\n",s[m]);

     return ;

 }

3157: 国王奇遇记

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 357  Solved: 196
[Submit][Status][Discuss]

Description

 

Input

共一行包括两个正整数N和M。

Output

共一行为所求表达式的值对10^9+7取模的值。

Sample Input

5 3

Sample Output

36363

HINT

1<=N<=10^9,1<=M<=200

Source

Katharon+#1

[Submit][Status][Discuss]