fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MOD = 1e9 + 7;
  5. const int MAXN = 2e6 + 5;
  6.  
  7. long long fact[MAXN], fib[MAXN], inv_pow2[MAXN];
  8.  
  9. long long modexp(long long a, long long e) {
  10.     long long r = 1;
  11.     while (e) {
  12.         if (e & 1) r = r * a % MOD;
  13.         a = a * a % MOD;
  14.         e >>= 1;
  15.     }
  16.     return r;
  17. }
  18.  
  19. int main() {
  20.     ios::sync_with_stdio(false);
  21.     cin.tie(NULL);
  22.  
  23.     // factorial
  24.     fact[0] = 1;
  25.     for (int i = 1; i < MAXN; i++)
  26.         fact[i] = fact[i - 1] * i % MOD;
  27.  
  28.     // fibonacci
  29.     fib[0] = 0;
  30.     fib[1] = 1;
  31.     for (int i = 2; i < MAXN; i++)
  32.         fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
  33.  
  34.     // inverse powers of 2
  35.     long long inv2 = modexp(2, MOD - 2);
  36.     inv_pow2[0] = 1;
  37.     for (int i = 1; i < MAXN; i++)
  38.         inv_pow2[i] = inv_pow2[i - 1] * inv2 % MOD;
  39.  
  40.     int t;
  41.     cin >> t;
  42.  
  43.     while (t--) {
  44.         int n;
  45.         cin >> n;
  46.         int m = 2 * n;
  47.  
  48.         vector<int> a(m);
  49.         for (int i = 0; i < m; i++) cin >> a[i];
  50.  
  51.         // check condition a[i] + a[i+1] == 2
  52.         bool ok = true;
  53.         for (int i = 0; i < m; i++) {
  54.             if (a[i] + a[(i + 1) % m] != 2) {
  55.                 ok = false;
  56.                 break;
  57.             }
  58.         }
  59.  
  60.         if (!ok) {
  61.             cout << 0 << '\n';
  62.             continue;
  63.         }
  64.  
  65.         // check if all ones
  66.         bool all_one = true;
  67.         for (int i = 0; i < m; i++) {
  68.             if (a[i] != 1) {
  69.                 all_one = false;
  70.                 break;
  71.             }
  72.         }
  73.  
  74.         long long res = fact[m] * inv_pow2[n] % MOD;
  75.  
  76.         if (all_one) {
  77.             res = res * fib[n + 1] % MOD;
  78.         }
  79.  
  80.         cout << res << '\n';
  81.     }
  82.  
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0.03s 50324KB
comments (?)
stdin
copy 
4
2
1 0 1 0
1
0 2
3
1 0 0 1 1 0
7
1 1 1 1 1 1 1 1 1 1 1 1 1 1
stdout
copy 
0
1
0
302688302
https://ideone.com/S9hvaJ
language:
C++14 (gcc 8.3)
created:
3 hours 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!