fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <set> // Used for conceptual clarity in merge, can be optimized
  5.  
  6. using namespace std;
  7.  
  8. long long power(long long base, long long exp) {
  9.     long long res = 1;
  10.     base %= 1000000007;
  11.     while (exp > 0) {
  12.         if (exp % 2 == 1) res = (res * base) % 1000000007;
  13.         base = (base * base) % 1000000007;
  14.         exp /= 2;
  15.     }
  16.     return res;
  17. }
  18.  
  19. long long inv(long long n) {
  20.     return power(n, 1000000007 - 2);
  21. }
  22.  
  23. const int MAX_N = 2005; // Adjust based on constraints if necessary
  24. long long fact[MAX_N];
  25. long long invFact[MAX_N];
  26. const long long MOD = 1000000007;
  27.  
  28. void precompute_factorials(int n) {
  29.     fact[0] = 1;
  30.     invFact[0] = 1;
  31.     for (int i = 1; i <= n; ++i) {
  32.         fact[i] = (fact[i - 1] * i) % MOD;
  33.         invFact[i] = inv(fact[i]); // Can optimize inv calculation
  34.     }
  35.     // Optimized inverse factorial calculation:
  36.     // invFact[n] = inv(fact[n]);
  37.     // for (int i = n - 1; i >= 0; --i) {
  38.     //     invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
  39.     // }
  40. }
  41.  
  42. long long nPr_mod(int n, int r) {
  43.     if (r < 0 || r > n) {
  44.         return 0;
  45.     }
  46.     long long num = fact[n];
  47.     long long den = invFact[n - r];
  48.     return (num * den) % MOD;
  49. }
  50.  
  51. // Global variables for precomputed data
  52. int n;
  53. vector<int> a;
  54. vector<int> pos;
  55. vector<bool> is_fixed;
  56. vector<bool> is_missing;
  57. vector<int> missing_numbers;
  58. vector<int> minus1_prefix;
  59. vector<int> missing_lt_k_count;
  60. int total_missing_count;
  61.  
  62. // --- Calculation Functions ---
  63.  
  64. long long calculate_count(int l, int r, int k) {
  65.     // Base case: k=0 means MEX >= 0, which is always true for non-empty subsegments.
  66.     // However, our sum starts from k=1 for V(l,r) = Sum_{k=1..n} Count(l,r,k)
  67.     if (k == 0) return 0; // Or handle differently if MEX=0 contribution needed elsewhere
  68.  
  69.     // 1. Check fixed numbers 0..k-1 are within [l,r]
  70.     for (int x = 0; x < k; ++x) {
  71.         if (is_fixed[x]) {
  72.             if (pos[x] < l || pos[x] > r) {
  73.                 return 0; // Fixed number required for MEX >= k is outside the segment
  74.             }
  75.         }
  76.     }
  77.  
  78.     // 2. Count required missing numbers (N_k)
  79.     int N_k = missing_lt_k_count[k];
  80.  
  81.     // 3. Count available -1 slots inside [l,r] (m_in)
  82.     int m_in = minus1_prefix[r + 1] - minus1_prefix[l];
  83.  
  84.     // 4. Check feasibility
  85.     if (m_in < N_k) {
  86.         return 0; // Not enough slots to place required missing numbers
  87.     }
  88.  
  89.     // 5. Calculate ways P(m_in, N_k) * (m - N_k)!
  90.     long long term1 = nPr_mod(m_in, N_k);
  91.     long long term2 = fact[total_missing_count - N_k];
  92.     long long result = (term1 * term2) % MOD;
  93.     return result;
  94. }
  95.  
  96. // Calculate V(l, r) = Sum_{k=1..n} Count(l, r, k)
  97. // This is O(N) per call.
  98. long long calculate_V(int l, int r) {
  99.     long long val_lr = 0;
  100.     for (int k = 1; k <= n; ++k) {
  101.         val_lr = (val_lr + calculate_count(l, r, k)) % MOD;
  102.     }
  103.     return val_lr;
  104. }
  105.  
  106.  
  107. // --- Divide and Conquer ---
  108.  
  109. // Naive O(N^3) merge step: iterates l, r and calls calculate_V (which is O(N))
  110. long long compute_crossing_sum_naive(int L, int mid, int R) {
  111.     long long crossing_sum = 0;
  112.     for (int l = mid; l >= L; --l) {
  113.         for (int r = mid + 1; r <= R; ++r) {
  114.             // O(N) calculation inside O(N^2) loops -> O(N^3)
  115.             long long val_lr = calculate_V(l, r);
  116.             crossing_sum = (crossing_sum + val_lr) % MOD;
  117.         }
  118.     }
  119.     return crossing_sum;
  120. }
  121.  
  122. // ** PLACEHOLDER for Optimized O(N^2) merge step **
  123. // This function would replace compute_crossing_sum_naive.
  124. // It requires efficiently calculating Sum_{l=L..mid, r=mid+1..R} Sum_{k=1..n} Count(l,r,k)
  125. // without the innermost O(N) loop over k for each (l,r).
  126. // This likely involves maintaining state (like running sums or bounds for k)
  127. // as l and r loops progress. The exact implementation is complex.
  128. /*
  129. long long compute_crossing_sum_optimized(int L, int mid, int R) {
  130.     long long crossing_sum = 0;
  131.     // Iterate l from mid down to L
  132.     for (int l = mid; l >= L; --l) {
  133.         // Maintain state for [l, mid] (fixed nums, -1 count)
  134.         // Iterate r from mid + 1 up to R
  135.         for (int r = mid + 1; r <= R; ++r) {
  136.             // Maintain state for [mid + 1, r] (fixed nums, -1 count)
  137.             // Combine states for [l, r]
  138.             // Efficiently update/calculate Sum_{k=1..n} Count(l, r, k)
  139.             // Add to crossing_sum
  140.         }
  141.     }
  142.     return crossing_sum;
  143. }
  144. */
  145.  
  146.  
  147. long long run_solve(int L, int R) {
  148.     if (L > R) {
  149.         return 0;
  150.     }
  151.     if (L == R) {
  152.         // Base case: Single element subsegment
  153.         return calculate_V(L, L);
  154.     }
  155.  
  156.     int mid = L + (R - L) / 2; // Avoid potential overflow
  157.  
  158.     long long res = (run_solve(L, mid) + run_solve(mid + 1, R)) % MOD;
  159.  
  160.     // *** Use the naive merge for now. Replace with optimized version if available ***
  161.     long long cross_sum = compute_crossing_sum_naive(L, mid, R);
  162.     // long long cross_sum = compute_crossing_sum_optimized(L, mid, R);
  163.  
  164.  
  165.     res = (res + cross_sum) % MOD;
  166.     return res;
  167. }
  168.  
  169. int main() {
  170.     ios_base::sync_with_stdio(false);
  171.     cin.tie(NULL);
  172.  
  173.     cin >> n;
  174.  
  175.     a.resize(n);
  176.     pos.assign(n, -1);
  177.     is_fixed.assign(n, false);
  178.     is_missing.assign(n, true); // Assume missing initially
  179.     minus1_prefix.assign(n + 1, 0);
  180.     missing_lt_k_count.assign(n + 1, 0);
  181.  
  182.     for (int i = 0; i < n; ++i) {
  183.         cin >> a[i];
  184.         minus1_prefix[i + 1] = minus1_prefix[i];
  185.         if (a[i] != -1) {
  186.             pos[a[i]] = i;
  187.             is_fixed[a[i]] = true;
  188.             is_missing[a[i]] = false;
  189.         } else {
  190.             minus1_prefix[i + 1]++;
  191.         }
  192.     }
  193.  
  194.     for (int i = 0; i < n; ++i) {
  195.         if (is_missing[i]) {
  196.             missing_numbers.push_back(i);
  197.         }
  198.     }
  199.     total_missing_count = missing_numbers.size();
  200.  
  201.     int current_missing_lt_k = 0;
  202.     for (int k = 0; k < n; ++k) {
  203.         if (is_missing[k]) {
  204.             current_missing_lt_k++;
  205.         }
  206.         missing_lt_k_count[k + 1] = current_missing_lt_k; // missing_lt_k_count[k] stores count < k
  207.     }
  208.  
  209.  
  210.     precompute_factorials(n); // Precompute up to n
  211.  
  212.     cout << run_solve(0, n - 1) << endl;
  213.  
  214.     return 0;
  215. }
Success #stdin #stdout 0.01s 5292KB
comments ()
stdin 
5
-1 0 -1 2 -1
stdout 
104
https://ideone.com/21orZr
language:
C++14 (gcc 8.3)
created:
19 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!