数论学习笔记
Posted On 2018年11月29日
自然数幂和
求\(\sum_{i=1}^{n}i^k\)
扰动法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <cstring> #include <iostream> using namespace std; typedef long long ll; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int P=1e9+7,up=1e6,maxn=up+100; inline int Pow(int a,int b) { int ans=1; for (;b;b>>=1,a=1ll*a*a%P)(b&1)&&(ans=1ll*ans*a%P); return ans; } int s[maxn],fac[maxn],inv[maxn]; inline int C(const int n,const int m) { return 1ll*fac[n]*inv[n-m]%P*inv[m]%P; } inline void dec(int&a,int delta) { a=a-delta; if (a<0)a+=P; } signed main() { int n=read(),k=read(); fac[0]=1; for (int i=1;i<=k+1;i++)fac[i]=1ll*fac[i-1]*i%P; inv[k+1]=Pow(fac[k+1],P-2); for (int i=k;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P; s[0]=n; for (int K=1;K<=k;K++) { dec(s[K]=Pow(n+1,K+1),1); for (int j=0;j<K;j++) dec(s[K],1ll*C(K+1,j)*s[j]%P); s[K]=1ll*s[K]*Pow(K+1,P-2)%P; } printf("%d\n",s[k]); } |
应用：BZOJ 3157: 国王奇遇记&&3516: 国王奇遇记加强版（扰动法）
Subscribe
0 评论