fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. const int MOD = 1e9 + 7;
  6.  
  7. vector<ll> fact, inv_fact;
  8.  
  9. ll mod_pow(ll a, ll b) {
  10.     ll res = 1;
  11.     while (b) {
  12.         if (b & 1) res = res * a % MOD;
  13.         a = a * a % MOD;
  14.         b >>= 1;
  15.     }
  16.     return res;
  17. }
  18.  
  19. ll mod_inv(ll a) {
  20.     return mod_pow(a, MOD - 2);
  21. }
  22.  
  23. void precompute(int n) {
  24.     fact.resize(n + 1);
  25.     inv_fact.resize(n + 1);
  26.     fact[0] = 1;
  27.     for (int i = 1; i <= n; ++i) {
  28.         fact[i] = fact[i - 1] * i % MOD;
  29.     }
  30.     inv_fact[n] = mod_inv(fact[n]);
  31.     for (int i = n - 1; i >= 0; --i) {
  32.         inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
  33.     }
  34. }
  35.  
  36. ll C(int n, int k) {
  37.     if (k < 0 || k > n) return 0;
  38.     return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
  39. }
  40.  
  41. int main() {
  42.     ios::sync_with_stdio(false);
  43.     cin.tie(nullptr);
  44.  
  45.     precompute(5000);
  46.  
  47.     int t;
  48.     cin >> t;
  49.     while (t--) {
  50.         int n;
  51.         cin >> n;
  52.         vector<int> a(n);
  53.         vector<bool> present(n, false);
  54.         int k = 0; // Number of missing elements
  55.         for (int i = 0; i < n; ++i) {
  56.             cin >> a[i];
  57.             if (a[i] == -1) {
  58.                 k++;
  59.             } else {
  60.                 present[a[i]] = true;
  61.             }
  62.         }
  63.  
  64.         vector<int> missing;
  65.         for (int x = 0; x < n; ++x) {
  66.             if (!present[x]) missing.push_back(x);
  67.         }
  68.  
  69.         ll total = 0;
  70.  
  71.         // For each possible mex m
  72.         for (int m = 0; m <= n; ++m) {
  73.             if (m > 0 && !present[m-1] && find(missing.begin(), missing.end(), m-1) == missing.end()) {
  74.                 continue; // m-1 is missing and not in missing list (impossible)
  75.             }
  76.  
  77.             bool mex_possible = true;
  78.             for (int x = 0; x < m; ++x) {
  79.                 if (!present[x] && find(missing.begin(), missing.end(), x) == missing.end()) {
  80.                     mex_possible = false;
  81.                     break;
  82.                 }
  83.             }
  84.             if (!mex_possible) continue;
  85.  
  86.             vector<int> pos_m;
  87.             if (m < n) {
  88.                 for (int i = 0; i < n; ++i) {
  89.                     if (a[i] == m) pos_m.push_back(i);
  90.                 }
  91.             }
  92.  
  93.             int cnt_m = pos_m.size();
  94.             if (cnt_m > 0) continue; // m is present in fixed positions, cannot be mex
  95.  
  96.             // Calculate the number of intervals [l, r] that can have mex m
  97.             // and the number of ways to fill the missing elements accordingly
  98.             // This part requires efficient interval counting, which can be done in O(n^2)
  99.             // Further optimization is needed here to reduce to O(n)
  100.             // [This is a placeholder for the actual optimized logic]
  101.         }
  102.  
  103.         cout << total << '\n';
  104.     }
  105.  
  106.     return 0;
  107. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5
2
0 -1
2
-1 -1
3
2 0 1
3
-1 2 -1
5
-1 0 -1 2 -1
stdout
copy 
0
0
0
0
0
https://ideone.com/9dft7d
language:
C++14 (gcc 8.3)
created:
11 days 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!