fork download
copy 
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <iostream>
  10.  
  11. using namespace std;
  12. const int Maxn = 1e4 + 1, Mod = 1e9 + 7;
  13. int fact[Maxn];
  14.  int ifact[Maxn];
  15.  int inv[Maxn];
  16. template<typename T, typename T1>
  17. T mod(T x, T1 p) {
  18.     x %= p;
  19.     if (x < 0)
  20.         x += p;
  21.     return x;
  22. }
  23.  
  24.  
  25.  
  26. // x must be relatively prime to p
  27. template<typename T>
  28. T inverse(T x, T p) {
  29.     x = mod(x, p);
  30.     if (x == 1)
  31.         return x;
  32.     return mod((1LL * (-p / x) * (inv[p % x] % p)) , p); 
  33.     // Since inverse of p % x is already calculated.
  34. }
  35.  
  36.  
  37. int NcR(int n, int r) {
  38.     int ret = (1LL * ifact[n - r] * ifact[r]) % Mod ;
  39. 	ret = (1LL * ret * fact[n]) % Mod;
  40.     return ret;
  41. }
  42. int power(int x, int y, int p) 
  43. { 
  44.     int res = 1;      // Initialize result 
  45.  
  46.     x = x % p;  // Update x if it is more than or  
  47.                 // equal to p 
  48.  
  49.     while (y > 0) 
  50.     { 
  51.         // If y is odd, multiply x with result 
  52.         if (y & 1) 
  53.             res = (res*x) % p; 
  54.  
  55.         // y must be even now 
  56.         y = y>>1; // y = y/2 
  57.         x = (x*x) % p;   
  58.     } 
  59.     return res; 
  60. } 
  61. int main()
  62. {
  63.  
  64. fact[0] = 1;
  65. for(int i = 1; i < Maxn; i++) {
  66. 	fact[i] = 1LL * fact[i - 1] * i % Mod;
  67. }
  68.  
  69.  
  70. ifact[0] = 1;
  71. for(int i = 1; i < Maxn; i++) {
  72. 	inv[i] = inverse(i, Mod);
  73. 	ifact[i] = (1LL * ifact[i - 1] * inv[i]) % Mod;
  74. }
  75.     int t;
  76.     cin>>t;
  77.     while(t--)
  78.     {
  79.         int n;
  80.         cin>>n;
  81.         int arr[n];
  82.         for(int i=0;i<n;i++)
  83.         cin>>arr[i];
  84.         int ans[n];
  85.         for(int i=0;i<n;i++)
  86.         {
  87.             int c=0;
  88.             for(int j=i;j<n;j++)
  89.             {
  90.                 int d =power(2,n-1-j,Mod);
  91.                 d=(d*arr[j])%Mod;
  92.                 if(i>0 and j>i)
  93.                 {
  94.                     d=(d*(int)NcR(j,i))%Mod;
  95.                 }
  96.                 c=(c+d)%Mod;
  97.             }
  98.             ans[i]=c;
  99.         }
  100.         for(int i=0;i<n;i++)
  101.         cout<<ans[i]<<" ";
  102.         cout<<endl;
  103.     }
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0s 4304KB
comments (?)
stdin
copy 
2
3
1 1 1
3
1 2 3
stdout
copy 
7 4 1 
11 10 3
https://ideone.com/xXiGr7
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!