fork download
copy 
  1. #include "bits/stdc++.h"
  2. using  namespace  std;
  3. typedef  long long ll;
  4. #define all(x) x.begin(), x.end()
  5. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  6.  
  7. const int N = 109;
  8. const int MOD = 1e9 + 7;
  9. ll c[N][N];
  10.  
  11. ll stars_and_bars(int n, int r){
  12.         //#ways to distribute n identical objects over r buckets
  13.         if(r == 0){
  14.                 //we have no buckets
  15.                 return !n;
  16.         }
  17.         return c[n + r - 1][n];
  18. }
  19. void solve(){
  20.         //generating the array randomly
  21.         int n = rng() % 25;
  22.         int a[n];
  23.         for(int i = 0; i < n; i++)
  24.                 a[i] = rng() % 1000;
  25.  
  26.  
  27.  
  28.         //The trivial O(n^2) solution
  29.         ll ans = 0;
  30.         for(int i = 0; i < n; i++){
  31.                 ll sum = 0;
  32.                 for(int j = i; j < n; j++){
  33.                         sum += a[j];
  34.                         int len = j - i + 1;
  35.                         ans += 1ll * len * len * len * sum % MOD;
  36.                         ans %= MOD;
  37.                 }
  38.         }
  39.         cout<<ans<<" ";
  40.         ans = 0;
  41.  
  42.         //The technique of ordered pairs solution
  43.         for(int i = 0; i < n; i++){
  44.                 int c = 0;
  45.                 for(int L = 0; L <= i; L++){
  46.                         for(int R = i; R < n; R++){
  47.                                 for(int x = L; x <= R; x++){
  48.                                         for(int y = L; y <= R; y++){
  49.                                                 for(int z = L; z <= R; z++){
  50.                                                         c++;
  51.                                                 }
  52.                                         }
  53.                                 }
  54.                         }
  55.                 }
  56.                 ans += c * a[i] % MOD;
  57.                 ans %= MOD;
  58.         }
  59.         cout<<ans<<" ";
  60.         ans = 0;
  61.  
  62.         //The optimization
  63.         for(int i = 0; i < n; i++){
  64.                 ll cc = 0;
  65.                 for(int L = 0; L <= 5; L++){
  66.                         for(int M = 0; M <= 5; M++){
  67.                                 int R = 5 - L - M;
  68.                                 if(R < 0) continue;
  69.                                 if(L + M > 0 && R + M > 0){
  70.                                         cc += stars_and_bars(L, i) * stars_and_bars(R, n - i - 1) % MOD;
  71.                                         cc %= MOD;
  72.                                 }
  73.                         }
  74.                 }
  75.                 ans += cc * a[i] % MOD;
  76.                 ans %= MOD;
  77.         }
  78.         cout<<ans<<"\n";
  79. }
  80. int main(){
  81.         cin.tie(0);
  82.         cin.sync_with_stdio(0);
  83.  
  84.         c[0][0] = 1;
  85.         for(int i = 1; i < N; i++){
  86.                 c[i][0] = 1;
  87.                 for(int j = 1; j <= i; j++)
  88.                         c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  89.         }
  90.  
  91.         int T; T = 4;
  92.         while(T--)
  93.                 solve();
  94. }
  95. /*
  96.  * Think twice, code once
  97.  * Think of different approaches to tackle a problem: write them down.
  98.  * Think of different views of the problem. don't look from only one side.
  99.  * don't get stuck in one approach.
  100.  * common mistakes: over_flow
  101.  *                  - out_of_bound index
  102.  *                  -infinite loop
  103.  *                  -corner cases
  104.  *                  -duplication counting.
  105.  */
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
946002381 946002381 197345148
57232 57232 24188
650408562 650408562 137246810
4518000 4518000 1240350
https://ideone.com/iBhJuA
language:
C++14 (gcc 8.3)
created:
2 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!