fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template <int MOD_> struct modnum {
  5. 	static constexpr int MOD = MOD_;
  6. 	static_assert(MOD_ > 0, "MOD must be positive");
  7.  
  8. private:
  9. 	using ll = long long;
  10.  
  11. 	int v;
  12.  
  13. 	static int minv(int a, int m) {
  14. 		a %= m;
  15. 		assert(a);
  16. 		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  17. 	}
  18.  
  19. public:
  20.  
  21. 	modnum() : v(0) {}
  22. 	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  23. 	explicit operator int() const { return v; }
  24. 	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  25. 	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  26.  
  27. 	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  28. 	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  29.  
  30. 	modnum inv() const {
  31. 		modnum res;
  32. 		res.v = minv(v, MOD);
  33. 		return res;
  34. 	}
  35. 	friend modnum inv(const modnum& m) { return m.inv(); }
  36. 	modnum neg() const {
  37. 		modnum res;
  38. 		res.v = v ? MOD-v : 0;
  39. 		return res;
  40. 	}
  41. 	friend modnum neg(const modnum& m) { return m.neg(); }
  42.  
  43. 	modnum operator- () const {
  44. 		return neg();
  45. 	}
  46. 	modnum operator+ () const {
  47. 		return modnum(*this);
  48. 	}
  49.  
  50. 	modnum& operator ++ () {
  51. 		v ++;
  52. 		if (v == MOD) v = 0;
  53. 		return *this;
  54. 	}
  55. 	modnum& operator -- () {
  56. 		if (v == 0) v = MOD;
  57. 		v --;
  58. 		return *this;
  59. 	}
  60. 	modnum& operator += (const modnum& o) {
  61. 		v += o.v;
  62. 		if (v >= MOD) v -= MOD;
  63. 		return *this;
  64. 	}
  65. 	modnum& operator -= (const modnum& o) {
  66. 		v -= o.v;
  67. 		if (v < 0) v += MOD;
  68. 		return *this;
  69. 	}
  70. 	modnum& operator *= (const modnum& o) {
  71. 		v = int(ll(v) * ll(o.v) % MOD);
  72. 		return *this;
  73. 	}
  74. 	modnum& operator /= (const modnum& o) {
  75. 		return *this *= o.inv();
  76. 	}
  77.  
  78. 	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  79. 	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  80. 	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  81. 	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  82. 	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  83. 	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  84. };
  85.  
  86. template <typename T> T pow(T a, long long b) {
  87. 	assert(b >= 0);
  88. 	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
  89. }
  90.  
  91. using num = modnum<int(1e9) + 7>;
  92.  
  93. const int MAXN = 1.1e5;
  94. const int MAXK = 11;
  95.  
  96. struct segtree {
  97. 	static const int S = 1<<18;
  98. 	struct seg_node {
  99. 		num sum;
  100. 		num m;
  101. 		num a;
  102. 	} seg[S*2];
  103.  
  104. 	void affine(int i, num m, num a, int len) {
  105. 		if (m == 1 && a == 0) return;
  106. 		auto& n = seg[i];
  107. 		n.sum *= m;
  108. 		n.sum += a * len;
  109. 		n.m *= m;
  110. 		n.a *= m;
  111. 		n.a += a;
  112. 	}
  113.  
  114. 	void propagate(int i, int len) {
  115. 		assert(i < S);
  116. 		auto& n = seg[i];
  117. 		if (n.m != 1 || n.a != 0) {
  118. 			affine(2*i, n.m, n.a, len/2);
  119. 			affine(2*i+1, n.m, n.a, len/2);
  120. 			n.m = 1, n.a = 0;
  121. 		}
  122. 	}
  123.  
  124. 	void update(int i, int l, int r, int ql, int qr, num m, num a) {
  125. 		if (qr <= l || r <= ql) return; 
  126. 		if (ql <= l && r <= qr) {
  127. 			affine(i, m, a, r-l);
  128. 		} else {
  129. 			propagate(i, r-l);
  130. 			int md = (l+r)/2;
  131. 			update(2*i, l, md, ql, qr, m, a);
  132. 			update(2*i+1, md, r, ql, qr, m, a);
  133. 			seg[i].sum = seg[2*i].sum + seg[2*i+1].sum;
  134. 		}
  135. 	}
  136.  
  137. 	num query(int i, int l, int r, int ql, int qr) {
  138. 		if (qr <= l || r <= ql) return 0; 
  139. 		if (ql <= l && r <= qr) {
  140. 			return seg[i].sum;
  141. 		} else {
  142. 			propagate(i, r-l);
  143. 			int md = (l+r)/2;
  144. 			return query(2*i, l, md, ql, qr) + query(2*i+1, md, r, ql, qr);
  145. 		}
  146. 	}
  147.  
  148. 	void update(int ql, int qr, num m, num a) {
  149. 		update(1, 0, S, ql, qr, m, a);
  150. 	}
  151.  
  152. 	num query(int ql, int qr) {
  153. 		return query(1, 0, S, ql, qr);
  154. 	}
  155. } segs[MAXK];
  156.  
  157. int N, K;
  158. pair<int, int> S[MAXN];
  159.  
  160. num stirling[MAXK][MAXK];
  161.  
  162. int main() {
  163. 	ios::sync_with_stdio(0), cin.tie(0);
  164.  
  165. 	cin >> N >> K;
  166. 	for (int i = 0; i < N; i++) {
  167. 		int l, r; cin >> l >> r;
  168. 		S[i] = {l,r};
  169. 	}
  170. 	sort(S, S+N);
  171.  
  172. 	segs[0].update(0, 1, 1, 1);
  173. 	for (int i = 0; i < N; i++) {
  174. 		int l, r; tie(l, r) = S[i];
  175.  
  176. 		for (int k = 0; k <= K; k++) {
  177. 			segs[k].update(r, r+1, 1, segs[k].query(0, r));
  178. 			if (k >= 1) {
  179. 				segs[k].update(r, r+1, 1, segs[k-1].query(0, l));
  180. 			}
  181. 			segs[k].update(r+1, 2*N+1, 2, 0);
  182. 		}
  183. 	}
  184.  
  185. 	stirling[0][0] = 1;
  186. 	for (int i = 1; i <= K; i++) {
  187. 		for (int j = 1; j <= i; j++) {
  188. 			stirling[i][j] = stirling[i-1][j-1] + stirling[i-1][j] * j;
  189. 		}
  190. 	}
  191.  
  192. 	num ans = 0;
  193. 	num fact = 1;
  194. 	for (int k = 1; k <= K; k++) {
  195. 		num tot = segs[k].seg[1].sum;
  196.  
  197. 		fact *= k;
  198. 		ans += fact * tot * stirling[K][k];
  199. 	}
  200. 	cout << ans << '\n';
  201.  
  202. 	return 0;
  203. }
  204.  
Success #stdin #stdout 0.02s 71292KB
comments (?)
stdin 
3 2
1 6
2 3
4 5
stdout 
10
https://ideone.com/4s6npw
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!