Dang_Quan_10_Tin

THT C (2021) permu

Oct 16th, 2021
513
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. constexpr int N = 1e5 + 5;
  7. constexpr ll mod = 1e9 + 7;
  8. pair<int, int> a[N], b[N];
  9. ll gt[N], rgt[N];
  10. int n, m, l(0);
  11.  
  12. void Read()
  13. {
  14.     cin >> n >> m;
  15.     for (int i = 1; i <= m; ++i)
  16.         cin >> a[i].first >> a[i].second;
  17.     sort(a + 1, a + m + 1);
  18. }
  19.  
  20. ll Pow(ll a, ll b)
  21. {
  22.     ll ans(1);
  23.     for (; b; b >>= 1)
  24.     {
  25.         if (b & 1)
  26.             ans = ans * a % mod;
  27.         a = a * a % mod;
  28.     }
  29.     return ans;
  30. }
  31.  
  32. ll C(int k, int n)
  33. {
  34.     return gt[n] * rgt[k] % mod * rgt[n - k];
  35. }
  36.  
  37. void Solve()
  38. {
  39.     gt[0] = 1;
  40.     for (int i = 1; i <= n; ++i)
  41.         gt[i] = gt[i - 1] * i % mod;
  42.     rgt[n] = Pow(gt[n], mod - 2);
  43.     for (int i = n - 1; ~i; --i)
  44.         rgt[i] = rgt[i + 1] * (i + 1) % mod;
  45.  
  46.     int cnt(0);
  47.     for (int i = 1, j = 1; i <= m; ++i)
  48.     {
  49.         int maxn = a[i].second;
  50.         while (j <= m && maxn >= a[j].first)
  51.         {
  52.             maxn = max(maxn, a[j].second);
  53.             ++j;
  54.         }
  55.         cnt += maxn - a[i].first + 1;
  56.         i = j - 1;
  57.     }
  58.  
  59.     ll ans(0);
  60.  
  61.     for (int i = 0; i <= cnt; ++i)
  62.     {
  63.         ans = (ans + ((i & 1) ? -1 : 1) * C(i, cnt) % mod * gt[n - i]) % mod;
  64.     }
  65.  
  66.     cout << (ans + mod) % mod;
  67. }
  68.  
  69. int32_t main()
  70. {
  71.     ios::sync_with_stdio(0);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.     Read();
  75.     Solve();
  76. }
RAW Paste Data