fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N=1e6+5,mod=1e9+7;
  5. int n,t;
  6. int A[N],fac[N],inv_fac[N],pre[N],suf[N];
  7. int pow(int x,int y)
  8. {
  9.     if(y==0) return 1ll;
  10.     int tmp=pow(x,y/2);
  11.     if(y&1) return 1ll*tmp*tmp%mod*x%mod;
  12.     else return 1ll*tmp*tmp%mod;
  13. }
  14. void calc()
  15. {
  16.     fac[0]=1;
  17.     for(int a=1;a<=200000;a++){
  18.         fac[a]=1ll*fac[a-1]*a%mod;
  19.     }
  20.     inv_fac[200000]=pow(fac[200000],mod-2);
  21.     for(int a=200000-1;a>=0;a--){
  22.         inv_fac[a]=1ll*inv_fac[a+1]*(a+1)%mod;
  23.     }
  24. }
  25. signed main()
  26. {
  27.     ios_base::sync_with_stdio(false); cin.tie(0);
  28.     calc();
  29.     cin>>n;
  30.     for(int a=0;a<=n;a++){
  31.         cin>>A[a];
  32.     }
  33.     cin>>t;
  34.     pre[0]=1;
  35.     for(int a=0;a<=n-1;a++){
  36.         pre[a+1]=1ll*pre[a]*(t-a)%mod;
  37.     }
  38.     suf[n+1]=1;
  39.     for(int a=n;a>=0;a--){
  40.         suf[a]=1ll*suf[a+1]*(t-a)%mod;
  41.     }
  42.     int sum=0;
  43.     for(int a=0;a<=n;a++){
  44.         int res=A[a];
  45.         res=1ll*res*pre[a]%mod;
  46.         res=1ll*res*suf[a+1]%mod;
  47.         res=1ll*res*inv_fac[n-a]%mod;
  48.         res=1ll*res*inv_fac[a]%mod;
  49.         if((n-a) & 1) sum-=res;
  50.         else sum+=res;
  51.         sum%=mod;
  52.     }
  53.     sum+=mod;
  54.     sum%=mod;
  55.     cout<<sum;
  56. }
  57.  
Success #stdin #stdout 0.01s 15908KB
comments (?)
stdin
copy 
5
4 16 106 484 1624 4384
1000000000
stdout
copy 
999984471
https://ideone.com/cvAdaj
language:
C++14 (gcc 8.3)
created:
1 day 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!