fork download
copy 
  1. /* 
  2.  * Author: sr1jan
  3.  * I shall taste the blood...
  4.  *
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define fi first
  10. #define se second
  11. #define sz(x) ((int)(x).size())
  12. #define all(x) (x).begin(),(x).end()
  13. #define rall(x) (x).rbegin(),(x).rend()
  14. #define mp make_pair
  15. #define pb push_back
  16.  
  17. typedef long long ll;
  18. // global 
  19.  
  20. // timer code
  21. /* auto start = chrono::high_resolution_clock::now(); */ 
  22. /* auto end = chrono::high_resolution_clock::now(); */ 
  23. /* double time_taken = chrono::duration_cast<chrono::nanoseconds>(end - start).count(); */ 
  24. /* time_taken *= 1e-9; */ 
  25. /* cout << time_taken << setprecision(9) << endl; */ 
  26.  
  27. ll gcd(ll a, ll b) {if(a==0) return b; return gcd(b%a, a);}
  28.  
  29. bool p_se_sort(pair<int,int> a, pair<int,int> b){
  30.     return a.second<b.second;
  31. }
  32.  
  33. inline bool ss(ll n){
  34.     if((n%4)==2||(n%4)==-2) return false;
  35.     return true;
  36. }
  37.  
  38. void solve(){
  39.     int n;
  40.     cin>>n;
  41.     vector<int> a(n);
  42.     vector<int> dp(n);
  43.     ll c=0;
  44.     for(int i=0, ai; i<n; ++i){
  45.         cin>>ai;
  46.         if(ss(ai)) ++c;
  47.         a[i]=ai;
  48.         dp[i]=ai%4;
  49.     }
  50.  
  51.     int k=2;
  52.     while(k<=n){
  53.         /* cout << "K: " << k << endl; */
  54.         for(int i=0; i<=n-k; i++){
  55.             if(dp[i+(k-1)]==0){
  56.                 ++c;
  57.                 continue;
  58.             }
  59.             dp[i+(k-1)] = (dp[i+(k-1)] * (a[i]%4)) % 4;
  60.             if(ss(dp[i+(k-1)])) ++c;
  61.         }
  62.         ++k;
  63.     }
  64.     cout << c << '\n';
  65. }
  66.  
  67. int main(){
  68.     ios_base::sync_with_stdio(false); 
  69.     cin.tie(NULL);
  70.     cout.tie(NULL);
  71.  
  72.     int t;
  73.     cin>>t;
  74.     while(t--){
  75.         solve();
  76.     }
  77.  
  78. }
  79.  
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
2
3
1 2 3
3
2 5 6
stdout
copy 
2
2
https://ideone.com/fnzvBG
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!