Advertisement
veschii_nevstrui

Untitled

Dec 20th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long mod = 998244353;
  6. vector <long long> fact;
  7. vector <long long> tcaf;
  8.  
  9. const int MAXN = 1e6 + 1;
  10.  
  11. long long cnk(int n, int k) {
  12.     return fact[n] * tcaf[k] % mod * tcaf[n - k] % mod;
  13. }
  14.  
  15. long long ans(int l, int r, vector <int> &left, vector <int> &right, map <pair <int, int>, int> &mp) {
  16.     if (l == r) {
  17.         return 1;
  18.     }
  19.     auto it = mp.find({l, r});
  20.     if (it == mp.end()) {
  21.         return 0;
  22.     }
  23.     int m = it->second;
  24.  
  25.     long long ans1 = ans(l, m, left, right, mp);
  26.     long long ans2 = ans(m + 1, r, left, right, mp);
  27.     return ans1 * ans2 % mod * cnk(r - l - 1, m - l) % mod;
  28. }
  29.  
  30. void solve() {
  31.     int n;
  32.     cin >> n;
  33.     vector <int> left(n), right(n);
  34.     for (auto &i: left) {
  35.         scanf("%d", &i);
  36.         --i;
  37.     }
  38.     for (auto &i: right) {
  39.         scanf("%d", &i);
  40.         --i;
  41.     }
  42.     map <pair <int, int>, int> mp;
  43.     for (int i = 0; i < n; ++i) {
  44.         mp[{left[i], right[i] + 1}] = i;
  45.     }
  46.     int a = ans(0, n, left, right, mp);
  47.     printf("%d\n", a);
  48. }
  49.  
  50. long long binpow(long long a, long long n) {
  51.     if (n == 0) {
  52.         return 1;
  53.     }
  54.     long long ans = binpow(a, n / 2);
  55.     ans = ans * ans % mod;
  56.     if (n % 2 == 1) {
  57.         ans = ans * a % mod;
  58.     }
  59.     return ans;
  60. }
  61.  
  62. int main() {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0);
  65.     cout.tie(0);
  66.  
  67.     fact.resize(MAXN);
  68.     tcaf.resize(MAXN);
  69.     fact[0] = 1;
  70.     tcaf[0] = 1;
  71.     for (int i = 1; i < MAXN; ++i) {
  72.         fact[i] = fact[i - 1] * i % mod;
  73.         tcaf[i] = binpow(fact[i], mod - 2);
  74.     }
  75.  
  76.     int t;
  77.     scanf("%d", &t);
  78.     for (int i = 0; i < t; ++i) {
  79.         solve();
  80.     }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement