fork 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.     inv_fact[n] = mod_inv(fact[n]);
  30.     for (int i = n - 1; i >= 0; --i)
  31.         inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
  32. }
  33.  
  34. ll C(int n, int k) {
  35.     return (k < 0 || k > n) ? 0 : fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
  36. }
  37.  
  38. int main() {
  39.     ios::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41.     precompute(5000);
  42.  
  43.     int t; cin >> t;
  44.     while (t--) {
  45.         int n; cin >> n;
  46.         vector<int> a(n);
  47.         vector<bool> present(n, false);
  48.         int total_missing = 0;
  49.         for (int i = 0; i < n; ++i) {
  50.             cin >> a[i];
  51.             if (a[i] == -1) {
  52.                 total_missing++;
  53.             } else {
  54.                 present[a[i]] = true;
  55.             }
  56.         }
  57.  
  58.         vector<int> missing;
  59.         for (int x = 0; x < n; ++x) {
  60.             if (!present[x]) missing.push_back(x);
  61.         }
  62.  
  63.         ll total = 0;
  64.  
  65.         for (int mex = 0; mex <= n; ++mex) {
  66.             // Проверка возможности MEX = mex
  67.             bool possible = true;
  68.             int required = 0; // Число обязательных пропусков для [0..mex-1]
  69.             for (int x = 0; x < mex; ++x) {
  70.                 if (!present[x]) {
  71.                     if (find(missing.begin(), missing.end(), x) == missing.end()) {
  72.                         possible = false;
  73.                         break;
  74.                     }
  75.                     required++;
  76.                 }
  77.             }
  78.             if (!possible) continue;
  79.  
  80.             // Проверка, что mex не присутствует в фиксированных элементах
  81.             if (mex < n && present[mex]) continue;
  82.  
  83.             // Подсчёт вклада для текущего mex
  84.             for (int l = 0; l < n; ++l) {
  85.                 int current_missing = 0;
  86.                 int cnt_has = 0;
  87.                 vector<bool> has(mex, false);
  88.                 bool invalid = false;
  89.  
  90.                 for (int r = l; r < n; ++r) {
  91.                     if (a[r] == -1) {
  92.                         current_missing++;
  93.                     } else {
  94.                         if (a[r] == mex) {
  95.                             invalid = true; // mex присутствует в подотрезке
  96.                         } else if (a[r] < mex && !has[a[r]]) {
  97.                             cnt_has++;
  98.                             has[a[r]] = true;
  99.                         }
  100.                     }
  101.  
  102.                     if (invalid) break;
  103.  
  104.                     // Проверяем, все ли [0..mex-1] присутствуют или могут быть добавлены
  105.                     int needed = required - (mex - cnt_has);
  106.                     if (needed < 0) needed = 0;
  107.                     if (current_missing >= needed) {
  108.                         ll ways = C(total_missing - needed, current_missing - needed);
  109.                         ways = ways * fact[required] % MOD; // Перестановки обязательных
  110.                         ways = ways * fact[total_missing - required] % MOD; // Остальные
  111.                         total = (total + ways * mex % MOD) % MOD;
  112.                     }
  113.                 }
  114.             }
  115.         }
  116.  
  117.         cout << total << '\n';
  118.     }
  119.     return 0;
  120. }
Success #stdin #stdout 0.01s 5288KB
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 
9
25
18
70
1950
https://ideone.com/NWVwls
language:
C++14 (gcc 8.3)
created:
12 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!