fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ull = unsigned long long;
  5.  
  6. typedef unsigned long long ul; typedef __uint128_t L;
  7. struct ModFast {
  8. 	ul b,m; ModFast(ul b_) : b(b_), m(ul((L(1)<<64)/b)) {}
  9. 	ul reduce(ul a) {
  10. 		ul q = (ul)((L(m)*a)>>64), r = a-q*b;
  11. 		return r>=b?r-b:r; }
  12. };
  13. ModFast MF(int(1e9) + 7);
  14.  
  15. template <int MOD_> struct modnum {
  16. 	static constexpr int MOD = MOD_;
  17. 	static_assert(MOD_ > 0, "MOD must be positive");
  18.  
  19. private:
  20. 	using ll = long long;
  21.  
  22. 	int v;
  23.  
  24. 	static int minv(int a, int m) {
  25. 		a %= m;
  26. 		assert(a);
  27. 		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  28. 	}
  29.  
  30. public:
  31.  
  32. 	modnum() : v(0) {}
  33. 	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  34. 	explicit operator int() const { return v; }
  35. 	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  36. 	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  37.  
  38. 	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  39. 	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  40.  
  41. 	modnum inv() const {
  42. 		modnum res;
  43. 		res.v = minv(v, MOD);
  44. 		return res;
  45. 	}
  46. 	friend modnum inv(const modnum& m) { return m.inv(); }
  47. 	modnum neg() const {
  48. 		modnum res;
  49. 		res.v = v ? MOD-v : 0;
  50. 		return res;
  51. 	}
  52. 	friend modnum neg(const modnum& m) { return m.neg(); }
  53.  
  54. 	modnum operator- () const {
  55. 		return neg();
  56. 	}
  57. 	modnum operator+ () const {
  58. 		return modnum(*this);
  59. 	}
  60.  
  61. 	modnum& operator ++ () {
  62. 		v ++;
  63. 		if (v == MOD) v = 0;
  64. 		return *this;
  65. 	}
  66. 	modnum& operator -- () {
  67. 		if (v == 0) v = MOD;
  68. 		v --;
  69. 		return *this;
  70. 	}
  71. 	modnum& operator += (const modnum& o) {
  72. 		v += o.v;
  73. 		if (v >= MOD) v -= MOD;
  74. 		return *this;
  75. 	}
  76. 	modnum& operator -= (const modnum& o) {
  77. 		v -= o.v;
  78. 		if (v < 0) v += MOD;
  79. 		return *this;
  80. 	}
  81. 	modnum& operator *= (const modnum& o) {
  82. 		v = MF.reduce(ull(v) * o.v);
  83. 		return *this;
  84. 	}
  85. 	modnum& operator /= (const modnum& o) {
  86. 		return *this *= o.inv();
  87. 	}
  88.  
  89. 	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  90. 	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  91. 	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  92. 	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  93. 	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  94. 	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  95. };
  96.  
  97. template <typename T> T pow(T a, long long b) {
  98. 	assert(b >= 0);
  99. 	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
  100. }
  101.  
  102. using num = modnum<int(1e9) + 7>;
  103.  
  104. const int MAXN = 5.1e4;
  105. int N, K;
  106. num pref[MAXN][20];
  107. num ipref[MAXN][20];
  108.  
  109. int Q;
  110.  
  111. int main() {
  112. 	ios::sync_with_stdio(0), cin.tie(0);
  113.  
  114. 	cin >> N >> K;
  115. 	num cur[20][20];
  116. 	num icur[20][20];
  117. 	for (int i = 0; i < K; i++) {
  118. 		for (int j = 0; j < K; j++) {
  119. 			cur[i][j] = icur[i][j] = (i == j);
  120. 		}
  121. 	}
  122. 	const num INV2 = num(2).inv();
  123. 	for (int z = 0; z <= N; z++) {
  124. 		for (int i = 0; i < K; i++) {
  125. 			for (int j = i; j < K; j++) {
  126. 				pref[z][i] += cur[i][j];
  127. 			}
  128. 		}
  129. 		for (int i = 0; i < K; i++) {
  130. 			ipref[z][i] = icur[0][i];
  131. 		}
  132. 		if (z == N) break;
  133.  
  134. 		int v; cin >> v; v--;
  135.  
  136. 		for (int i = 0; i <= v; i++) {
  137. 			for (int j = v; j >= i; j--) {
  138. 				cur[i][v] += cur[i][j];
  139. 			}
  140. 		}
  141.  
  142. 		for (int i = 0; i < v; i++) {
  143. 			for (int j = v; j < K; j++) {
  144. 				icur[i][j] -= INV2 * icur[v][j];
  145. 			}
  146. 		}
  147. 		for (int i = v; i < K; i++) {
  148. 			icur[v][i] *= INV2;
  149. 		}
  150. 	}
  151.  
  152. 	cin >> Q;
  153. 	while (Q--) {
  154. 		int l, r; cin >> l >> r; l--;
  155. 		num res = 0;
  156. 		for (int i = 0; i < K; i++) {
  157. 			res += ipref[l][i] * pref[r][i];
  158. 		}
  159. 		cout << res << '\n';
  160. 	}
  161.  
  162. 	return 0;
  163. }
  164.  
Success #stdin #stdout 0.01s 11680KB
comments (?)
stdin
copy 
5 2
1 2 1 1 2
3
2 3
4 5
1 5
stdout
copy 
3
4
20
https://ideone.com/22ImH1
language:
C++14 (gcc 8.3)
created:
4 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!