fork download
copy 
  1. // LUOGU_RID: 157318629
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int N=1e6+10;
  8. const int mod=1e9+7;
  9. ll y[N],fac[N],inv[N],pre[N],suf[N];
  10. int n,k;
  11. ll ans;
  12.  
  13. ll q_pow(ll a,ll b)
  14. {
  15.     ll res=1;
  16.     while(b)
  17.     {
  18.         if(b&1) res=(res*a)%mod;
  19.         a=(a*a)%mod;
  20.         b>>=1;
  21.     }
  22.     return res;
  23. }
  24.  
  25. int main()
  26. {
  27.     cin>>n>>k;
  28.     for(int i=1; i<=k+2; i++)
  29.         y[i]=(y[i-1]+q_pow(i,k))%mod;
  30.  
  31.     fac[0]=1;
  32.     for(int i=1; i<=k+3; i++) fac[i]=fac[i-1]*i%mod;
  33.  
  34.     pre[0]=1,suf[k+3]=1;
  35.     for(int i=1; i<=k+2; i++) pre[i]=pre[i-1]*(n-i)%mod;
  36.     for(int i=k+2; i>=1; i--) suf[i]=suf[i+1]*(n-i)%mod;
  37.  
  38.     inv[k+3]=q_pow(fac[k+3],mod-2);
  39.     for(int i=k+2;i+1>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
  40.  
  41.  
  42.     for(int i=1;i<=k+2;i++)
  43.     {
  44.         ll t=y[i]*pre[i-1]%mod;
  45.         t=t*suf[i+1]%mod;
  46.         t=t*inv[i-1]%mod;
  47.         t=t*inv[k+2-i]%mod;
  48.         if((k+2-i)&1) ans=(ans-t+mod)%mod;
  49.         else ans=(ans+t)%mod;
  50.     }
  51.  
  52.     cout<<ans<<endl;
  53.  
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0.01s 9788KB
comments (?)
stdin
copy 
1 4
stdout
copy 
1
https://ideone.com/Fkmld0
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!