1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
| #include <cstdio> #include <vector> #include <algorithm> #define fi first #define se second #define pb push_back using namespace std; template <class Type> void read (Type &x) { char c; bool flag = false; while ((c = getchar()) < '0' || c > '9') c == '-' && (flag = true); x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - '0'; flag && (x = ~x + 1); } template <class Type, class ...rest> void read (Type &x, rest &...y) { read(x), read(y...); } template <class Type> void write (Type x) { x < 0 && (putchar('-'), x = ~x + 1); x > 9 && (write(x / 10), 0); putchar('0' + x % 10); } typedef long long LL; typedef pair <int, int> PII; const int N = 510, mod = 1e9 + 7; PII p[N]; int n, m, C[N], f[N], inv[N]; void init () { inv[1] = 1; for (int i = 2; i < N; ++i) inv[i] = -(LL)(mod / i) * inv[mod % i] % mod; } int main () { init(); read(n); vector <int> ws; for (int i = 1; i <= n; ++i) { read(p[i].fi, p[i].se); ws.pb(p[i].fi), ws.pb(++p[i].se); } sort(ws.begin(), ws.end()); m = ws.erase(unique(ws.begin(), ws.end()), ws.end()) - ws.begin(); for (int i = 1; i <= n; ++i) { p[i].fi = lower_bound(ws.begin(), ws.end(), p[i].fi) - ws.begin(); p[i].se = lower_bound(ws.begin(), ws.end(), p[i].se) - ws.begin(); } f[0] = 1; for (int i = 1; i < m; ++i) { C[0] = 1; for (int j = 1, t = ws[i] - ws[i - 1]; j <= n; ++j, ++t) C[j] = (LL)C[j - 1] * t % mod * inv[j] % mod; for (int j = n; j; --j) if (p[j].fi <= i - 1 && p[j].se >= i) { int s = 0, c = 1; for (int k = j - 1; ~k; --k) { s = (s + (LL)C[c] * f[k]) % mod; if (p[k].fi <= i - 1 && p[k].se >= i) ++c; } f[j] = (f[j] + s) % mod; } } int res = 0; for (int i = 1; i <= n; ++i) res = (res + f[i]) % mod; write((res + mod) % mod); return 0; }
|
Gitalk 加载中 ...