Advertisement
ashmelev

E

Mar 20th, 2023
730
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <map>
  8. #include <set>
  9. #include <bitset>
  10. #include <queue>
  11. #include <stack>
  12. #include <sstream>
  13. #include <cstring>
  14. #include <numeric>
  15. #include <ctime>
  16. #include <cassert>
  17. #include <random>
  18. //#include <valarray>
  19. //#include <fstream>
  20.  
  21. #define re return
  22. #define fi first
  23. #define se second
  24. #define mp make_pair
  25. #define pb emplace_back
  26. #define all(x) x.begin(), x.end()
  27. #define sz(x) ((int)(x).size())
  28. #define rep(i, n) for (int i = 0; i < (n); i++)
  29. #define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
  30. #define y0 y32479
  31. #define y1 y95874
  32. #define next next239
  33. #define prev prev239
  34. #define fill(x, y) memset(x, y, sizeof(x))
  35. #define sqr(x) ((x)*(x))
  36. #define sqrt(x) sqrt(abs(x))
  37. #define unq(x) (x.resize(unique(all(x)) - x.begin()))
  38. #define ba back()
  39. #define popcount __builtin_popcountll
  40. #define firstbit(x) (63 - __builtin_clzll(x))
  41. #define fastIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
  42.  
  43. #ifdef LOCAL_BOBER
  44. bool local = true;
  45. #define deb(x) cout << #x << " = " << (x) << endl
  46. #define debn(x, n) { cout << #x << "(" << n << ") = " << \
  47.     "{"; int _f_ = 1; rep(_i_, n) {if (!_f_) cout << "|"; cout << x[_i_]; _f_= 0;} cout << "}" << endl;}
  48. #define deba(x) { cout << #x << " (size: " << sz(x) << ") = " << \
  49.     "{"; int _f_ = 1; for (auto o : x) {if (!_f_) cout << "|"; cout << o; _f_ = 0;} cout << "}" << endl;}
  50. #else
  51. bool local = false;
  52. #define deb(x) ;
  53. #define debn(x, n) ;
  54. #define deba(x) ;
  55. #define endl "\n"
  56. #endif
  57.  
  58. using namespace std;
  59.  
  60. typedef vector<int> vi;
  61. typedef vector<vi> vvi;
  62. typedef pair<int, int> ii;
  63. typedef vector<ii> vii;
  64. typedef vector<string> vs;
  65. typedef long long ll;
  66. typedef pair<ll, ll> pll;
  67. typedef vector<ll> vll;
  68. typedef pair<double, double> pdd;
  69. typedef long double LD;
  70. typedef double D;
  71.  
  72. template<class T> void print(T v) { cout << sz(v) << endl; for (auto x : v) cout << x << ' '; cout << endl; };
  73. template<class T> void print1(T v) { cout << sz(v) << endl; for (auto x : v) cout << x + 1 << ' '; cout << endl; };
  74. template<class T1, class T2> ostream& operator << (ostream &o, pair<T1, T2> x) {re o << x.fi << ' ' << x.se;}
  75. template<class T1, class T2> istream& operator >> (istream &o, pair<T1, T2> &x) {re o >> x.fi >> x.se;}
  76. template<class T> ostream& operator << (ostream &o, vector<T> &x) {for (auto &el : x) o << el << ' '; re o;}
  77. template<class T> istream& operator >> (istream &o, vector<T> &x) {for (auto &el : x) o >> el; re o;}
  78. template<class T1, class T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se; re a;}
  79. template<class T1, class T2> pair<T1, T2> operator - (pair<T1, T2> a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se; re a;}
  80. template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
  81. template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}
  82.  
  83. int nint() {int x; cin >> x; re x;}
  84. double getTime() { re clock() / (double) CLOCKS_PER_SEC;};
  85.  
  86. mt19937 rnd(0);
  87. int rand(int n) { re rnd() % n; }
  88. int rand(int l, int r) { re rnd() % (r - l + 1) + l; }
  89.  
  90. //const int mod = 1000000000 + 7;
  91. const int mod = 998244353;
  92.  
  93. void initIO() {
  94.     if (local) {
  95.         freopen("input.txt", "r", stdin);
  96.         //freopen("output.txt", "w", stdout);
  97.         srand((int)time(0));
  98.         rnd.seed((int)time(0));
  99.     }
  100.     else {
  101.         //freopen("input.txt", "r", stdin);
  102.         //freopen("output.txt", "w", stdout);
  103.         fastIO();
  104.     }
  105. }
  106.  
  107. void solve();
  108. void precalc();
  109.  
  110. int TID;
  111.  
  112. signed main() {
  113.     initIO();
  114.  
  115.     int tc = 1;
  116. //  cin >> tc;
  117.  
  118.     precalc();
  119.     rep(tt, tc) {
  120.         TID = tt;
  121. //      cout << "Case #" << tt + 1 << ": ";
  122.         solve();
  123.     }
  124.  
  125.     if (local)
  126.         cout << endl << "time = " << getTime() << endl;
  127. }
  128.  
  129. void precalc() {
  130.  
  131. }
  132.  
  133. /* ================ actual code starts here ================ */
  134.  
  135. int n;
  136. int m;
  137.  
  138. int table[55][105][55];
  139. int l1[55], r1[55];
  140. int l[55], r[55];
  141. vi v;
  142.  
  143. ll st(ll x, ll p) {
  144.     ll ans = 1;
  145.     while (p) {
  146.         if (p & 1)
  147.             ans = ans * x % mod;
  148.         p /= 2;
  149.         x = x * x % mod;
  150.     }
  151.     re ans;
  152. }
  153.  
  154. ll get(int id, int k) {
  155.  
  156.     int len = v[id + 1] - v[id];
  157.  
  158.     len += k;
  159.     ll ans = 1;
  160.     for (int i = 1; i <= k; i++) {
  161.         ans = ans * (len - i) % mod;
  162.         ans = ans * st(i, mod - 2) % mod;
  163.     }
  164. //  cout << id << ' ' << k << ' ' << ans << endl;
  165.     re ans;
  166. }
  167.  
  168. int getans(int p, int id, int k) {
  169.     int &ans = table[p][id][k];
  170.     if (ans != -1)
  171.         re ans;
  172.  
  173. //  cout << p << ' ' << id << ' ' << k << endl;
  174.     if (p == n) {
  175.         ans = get(id, k);
  176.         re ans;
  177.     }
  178.  
  179.     ans = 0;
  180.     ll tmp = get(id, k);
  181.     if (id == 0)
  182.         tmp = 1;
  183.     deb(tmp);
  184.     for (int i = id + 1; i < r1[p]; i++) {
  185.         if (i < l1[p])
  186.             continue;
  187.         ans += getans(p + 1, i, 1) * tmp % mod;
  188.         if (ans >= mod)
  189.             ans -= mod;
  190.     }
  191.     if (id < r1[p] && id >= l1[p]) {
  192.         ans += getans(p + 1, id, k + 1);
  193.         if (ans >= mod)
  194.             ans -= mod;
  195.     }
  196.     re ans;
  197. }
  198.  
  199. void solve() {
  200.     cin >> n;
  201.     v.pb(-1);
  202.     rep(i, n) {
  203.         cin >> l[i] >> r[i];
  204.         r[i]++;
  205.         v.pb(l[i]);
  206.         v.pb(r[i]);
  207.     }
  208.     sort(all(v));
  209.     unq(v);
  210.     deba(v);
  211.     rep(i, n) {
  212.         l1[i] = lower_bound(all(v), l[i]) - v.begin();
  213.         r1[i] = lower_bound(all(v), r[i]) - v.begin();
  214. //      cout << i << ' ' << l1[i] << ' ' << r1[i] << endl;
  215.     }
  216.     fill(table, -1);
  217.     cout << getans(0, 0, 1);
  218. }
  219.  
  220.  
  221.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement