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.     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 k = 0; // Число пропусков (-1)
  49.         for (int i = 0; i < n; ++i) {
  50.             cin >> a[i];
  51.             if (a[i] == -1) k++;
  52.             else present[a[i]] = true;
  53.         }
  54.  
  55.         vector<int> missing;
  56.         for (int x = 0; x < n; ++x)
  57.             if (!present[x]) missing.push_back(x);
  58.  
  59.         ll total = 0;
  60.  
  61.         // Для каждого возможного mex m
  62.         for (int m = 0; m <= n; ++m) {
  63.             // Проверка, что все числа [0..m-1] присутствуют или могут быть заполнены
  64.             bool possible = true;
  65.             for (int x = 0; x < m; ++x)
  66.                 if (!present[x] && find(missing.begin(), missing.end(), x) == missing.end())
  67.                     possible = false;
  68.             if (!possible) continue;
  69.  
  70.             // Если m есть в фиксированных элементах, mex не может быть m
  71.             if (m < n && present[m]) continue;
  72.  
  73.             // Число обязательных пропусков: элементы < m, которые отсутствуют
  74.             int s = 0;
  75.             for (int x = 0; x < m; ++x)
  76.                 if (!present[x]) s++;
  77.  
  78.             // Обработка всех подотрезков [l, r]
  79.             for (int l = 0; l < n; ++l) {
  80.                 int cnt_missing = 0;
  81.                 set<int> current;
  82.                 for (int r = l; r < n; ++r) {
  83.                     if (a[r] == -1) cnt_missing++;
  84.                     else if (a[r] < m) current.insert(a[r]);
  85.  
  86.                     // Проверка условий для mex = m
  87.                     if (current.size() == m && (m == n || !current.count(m))) {
  88.                         // Число пропусков в подотрезке: need >= s
  89.                         if (cnt_missing >= s) {
  90.                             ll ways = C(k - s, cnt_missing - s);
  91.                             total = (total + ways * fact[k - s] % MOD * m % MOD) % MOD;
  92.                         }
  93.                     }
  94.                 }
  95.             }
  96.         }
  97.  
  98.         cout << total << '\n';
  99.     }
  100. }
Success #stdin #stdout 0.01s 5292KB
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 
2
0
3
0
120
https://ideone.com/xwq8d0
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!