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

时间:2024-09-01 20:05:02

数论


  题解: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

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

Input

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

Output

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

Sample Input

5 3

Sample Output

36363

HINT

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

Source

[Submit][Status][Discuss]