Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <set>
- #include <bitset>
- #include <queue>
- #include <stack>
- #include <sstream>
- #include <cstring>
- #include <numeric>
- #include <ctime>
- #include <cassert>
- #include <random>
- //#include <valarray>
- //#include <fstream>
- #define re return
- #define fi first
- #define se second
- #define mp make_pair
- #define pb emplace_back
- #define all(x) x.begin(), x.end()
- #define sz(x) ((int)(x).size())
- #define rep(i, n) for (int i = 0; i < (n); i++)
- #define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
- #define y0 y32479
- #define y1 y95874
- #define next next239
- #define prev prev239
- #define fill(x, y) memset(x, y, sizeof(x))
- #define sqr(x) ((x)*(x))
- #define sqrt(x) sqrt(abs(x))
- #define unq(x) (x.resize(unique(all(x)) - x.begin()))
- #define ba back()
- #define popcount __builtin_popcountll
- #define firstbit(x) (63 - __builtin_clzll(x))
- #define fastIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
- #ifdef LOCAL_BOBER
- bool local = true;
- #define deb(x) cout << #x << " = " << (x) << endl
- #define debn(x, n) { cout << #x << "(" << n << ") = " << \
- "{"; int _f_ = 1; rep(_i_, n) {if (!_f_) cout << "|"; cout << x[_i_]; _f_= 0;} cout << "}" << endl;}
- #define deba(x) { cout << #x << " (size: " << sz(x) << ") = " << \
- "{"; int _f_ = 1; for (auto o : x) {if (!_f_) cout << "|"; cout << o; _f_ = 0;} cout << "}" << endl;}
- #else
- bool local = false;
- #define deb(x) ;
- #define debn(x, n) ;
- #define deba(x) ;
- #define endl "\n"
- #endif
- using namespace std;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int, int> ii;
- typedef vector<ii> vii;
- typedef vector<string> vs;
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef vector<ll> vll;
- typedef pair<double, double> pdd;
- typedef long double LD;
- typedef double D;
- template<class T> void print(T v) { cout << sz(v) << endl; for (auto x : v) cout << x << ' '; cout << endl; };
- template<class T> void print1(T v) { cout << sz(v) << endl; for (auto x : v) cout << x + 1 << ' '; cout << endl; };
- template<class T1, class T2> ostream& operator << (ostream &o, pair<T1, T2> x) {re o << x.fi << ' ' << x.se;}
- template<class T1, class T2> istream& operator >> (istream &o, pair<T1, T2> &x) {re o >> x.fi >> x.se;}
- template<class T> ostream& operator << (ostream &o, vector<T> &x) {for (auto &el : x) o << el << ' '; re o;}
- template<class T> istream& operator >> (istream &o, vector<T> &x) {for (auto &el : x) o >> el; re o;}
- 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;}
- 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;}
- template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
- template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}
- int nint() {int x; cin >> x; re x;}
- double getTime() { re clock() / (double) CLOCKS_PER_SEC;};
- mt19937 rnd(0);
- int rand(int n) { re rnd() % n; }
- int rand(int l, int r) { re rnd() % (r - l + 1) + l; }
- //const int mod = 1000000000 + 7;
- const int mod = 998244353;
- void initIO() {
- if (local) {
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- srand((int)time(0));
- rnd.seed((int)time(0));
- }
- else {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- fastIO();
- }
- }
- void solve();
- void precalc();
- int TID;
- signed main() {
- initIO();
- int tc = 1;
- // cin >> tc;
- precalc();
- rep(tt, tc) {
- TID = tt;
- // cout << "Case #" << tt + 1 << ": ";
- solve();
- }
- if (local)
- cout << endl << "time = " << getTime() << endl;
- }
- void precalc() {
- }
- /* ================ actual code starts here ================ */
- int n;
- int m;
- int table[55][105][55];
- int l1[55], r1[55];
- int l[55], r[55];
- vi v;
- ll st(ll x, ll p) {
- ll ans = 1;
- while (p) {
- if (p & 1)
- ans = ans * x % mod;
- p /= 2;
- x = x * x % mod;
- }
- re ans;
- }
- ll get(int id, int k) {
- int len = v[id + 1] - v[id];
- len += k;
- ll ans = 1;
- for (int i = 1; i <= k; i++) {
- ans = ans * (len - i) % mod;
- ans = ans * st(i, mod - 2) % mod;
- }
- // cout << id << ' ' << k << ' ' << ans << endl;
- re ans;
- }
- int getans(int p, int id, int k) {
- int &ans = table[p][id][k];
- if (ans != -1)
- re ans;
- // cout << p << ' ' << id << ' ' << k << endl;
- if (p == n) {
- ans = get(id, k);
- re ans;
- }
- ans = 0;
- ll tmp = get(id, k);
- if (id == 0)
- tmp = 1;
- deb(tmp);
- for (int i = id + 1; i < r1[p]; i++) {
- if (i < l1[p])
- continue;
- ans += getans(p + 1, i, 1) * tmp % mod;
- if (ans >= mod)
- ans -= mod;
- }
- if (id < r1[p] && id >= l1[p]) {
- ans += getans(p + 1, id, k + 1);
- if (ans >= mod)
- ans -= mod;
- }
- re ans;
- }
- void solve() {
- cin >> n;
- v.pb(-1);
- rep(i, n) {
- cin >> l[i] >> r[i];
- r[i]++;
- v.pb(l[i]);
- v.pb(r[i]);
- }
- sort(all(v));
- unq(v);
- deba(v);
- rep(i, n) {
- l1[i] = lower_bound(all(v), l[i]) - v.begin();
- r1[i] = lower_bound(all(v), r[i]) - v.begin();
- // cout << i << ' ' << l1[i] << ' ' << r1[i] << endl;
- }
- fill(table, -1);
- cout << getans(0, 0, 1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement