API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 9th, 2022
156
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.68 KB | None | 0 0
raw download clone embed print report
  1. // Problem: B. Subway Pursuit
  2. // Contest: Codeforces - Codeforces Round #507 (Div. 1, based on Olympiad of Metropolises)
  3. // URL: https://codeforces.com/contest/1039/problem/B
  4. // Memory Limit: 512 MB
  5. // Time Limit: 2000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #include <bits/stdc++.h> //Blitztage
  10. using namespace std;
  11.  
  12. //for loop macros
  13. #define fo(i,n) for(int i = 0; i < n; i++)
  14. #define foL(i,n) for(long long i = 0; i < n; i++)
  15. #define foa(i,k,n) for(int i = k; i < n; i++)
  16. #define fob(i,k,n) for(int i = k; i >= n; i--)
  17. #define foaL(i,k,n) for(long long i = k; i < n; i++)
  18. #define fobL(i,k,n) for(long long i = k; i >= n; i--)
  19.  
  20. constexpr int bits(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);}
  21.  
  22. //template -> AnandOza && bqi343 Github
  23. #define pb push_back
  24. #define eb emplace_back
  25. #define mp make_pair
  26. #define F first
  27. #define S second
  28. #define resz resize
  29.  
  30. #define sz(x) int((x).size())
  31. #define all(x) (x).begin(), (x).end()
  32. #define rall(x) (x).rbegin(), (x).rend()
  33. #define trav(a, x) for (auto &a : x)
  34.  
  35. #define L1(u, ...) [&](auto &&u) { return __VA_ARGS__; }
  36. #define L2(u, v, ...) [&](auto &&u, auto &&v) { return __VA_ARGS__; }
  37.  
  38. #define sort_by(x, y) sort(all(x), [&](const auto &l, const auto &r) { return y; })
  39.  
  40. #define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
  41.  
  42. using ld = long double;
  43. using ll = long long;
  44. using vi = vector<int>;
  45. using vvi = vector<vi>;
  46. using vll = vector<ll>;
  47. using vvll = vector<vll>;
  48. using vb = vector<bool>;
  49. using vvb = vector<vb>;
  50. using vd = vector<double>;
  51. using vs = vector<string>;
  52.  
  53. using pii = pair<int, int>;
  54. using pll = pair<ll, ll>;
  55. using pdd = pair<double, double>;
  56.  
  57. using vpii = vector<pii>;
  58. using vpll = vector<pll>;
  59. using vpdd = vector<pdd>;
  60.  
  61. template <typename T> void ckmin(T &a, const T &b) { a = min(a, b); }
  62. template <typename T> void ckmax(T &a, const T &b) { a = max(a, b); }
  63.  
  64. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  65.  
  66. namespace __input {
  67. template <class T1, class T2> void re(pair<T1, T2> &p);
  68. template <class T> void re(vector<T> &a);
  69. template <class T, size_t SZ> void re(array<T, SZ> &a);
  70.  
  71. template <class T> void re(T &x) { cin >> x; }
  72. void re(double &x) { string t; re(t); x = stod(t); }
  73. template <class Arg, class... Args> void re(Arg &first, Args &...rest) { re(first); re(rest...); }
  74.  
  75. template <class T1, class T2> void re(pair<T1, T2> &p) { re(p.f, p.s); }
  76. template <class T> void re(vector<T> &a) { for (int i = 0; i < sz(a); i++) re(a[i]); }
  77. template <class T, size_t SZ> void re(array<T, SZ> &a) { for (int i = 0; i < SZ; i++) re(a[i]); }
  78. }
  79. using namespace __input;
  80.  
  81. namespace __output {
  82. template <typename T> struct is_outputtable { template <typename C> static constexpr decltype(declval<ostream &>() << declval<const C &>(), bool()) test(int) { return true; } template <typename C> static constexpr bool test(...) { return false; } static constexpr bool value = test<T>(int()); };
  83. template <class T, typename V = decltype(declval<const T &>().begin()), typename S = typename enable_if<!is_outputtable<T>::value, bool>::type> void pr(const T &x);
  84.  
  85. template <class T, typename V = decltype(declval<ostream &>() << declval<const T &>())> void pr(const T &x) { cout << x; }
  86. template <class T1, class T2> void pr(const pair<T1, T2> &x);
  87. template <class Arg, class... Args> void pr(const Arg &first, const Args &...rest) { pr(first); pr(rest...); }
  88.  
  89. template <class T, bool pretty = true> void prContain(const T &x) { if (pretty) pr("{"); bool fst = 1; for (const auto &a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0; if (pretty) pr("}"); }
  90.  
  91. template <class T> void pc(const T &x) { prContain<T, false>(x); pr("\n"); }
  92. template <class T1, class T2> void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }
  93. template <class T, typename V, typename S> void pr(const T &x) { prContain(x); }
  94.  
  95. void ps() { pr("\n"); }
  96. template <class Arg> void ps(const Arg &first) { pr(first); ps(); }
  97. template <class Arg, class... Args> void ps(const Arg &first, const Args &...rest) { pr(first, " "); ps(rest...); }
  98. }
  99. using namespace __output;
  100.  
  101. #define __pn(x) pr(#x, " = ")
  102. #ifdef ANAND_LOCAL
  103. #define pd(...) __pn((__VA_ARGS__)), ps(__VA_ARGS__), cout << flush
  104. #else
  105. #define pd(...)
  106. #endif
  107.  
  108. namespace __algorithm {
  109. template <typename T> void dedup(vector<T> &v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }
  110. template <typename T> typename vector<T>::const_iterator find(const vector<T> &v, const T &x) { auto it = lower_bound(all(v), x); return it != v.end() && *it == x ? it : v.end(); }
  111. template <typename T> size_t index(const vector<T> &v, const T &x) { auto it = find(v, x); assert(it != v.end() && *it == x); return it - v.begin(); }
  112. template <typename I> struct _reversed_struct { I &v_; explicit _reversed_struct(I &v) : v_{v} {} typename I::reverse_iterator begin() const { return v_.rbegin(); } typename I::reverse_iterator end() const { return v_.rend(); } };
  113. template <typename I> _reversed_struct<I> reversed(I &v) { return _reversed_struct<I>(v); }
  114. }
  115. using namespace __algorithm;
  116.  
  117. namespace __io {
  118. void setIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout << setprecision(15); }
  119. }
  120. using namespace __io;
  121.  
  122. template<typename T_vector>
  123. void outvec(const T_vector &v, bool add_one = false, int start = -1, int end = -1) {
  124. if (start < 0) start = 0;
  125. if (end < 0) end = int(v.size());
  126.  
  127. for (int i = start; i < end; i++)
  128. cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
  129. }
  130.  
  131. //#define int long long
  132.  
  133. #define noo {ps("NO");return;}
  134. #define yess {ps("YES");return;}
  135.  
  136. #define GOOGLE 0
  137. const ld pi = 3.14159265358979323846;
  138. const ll N = 7e5;
  139. //Global declarations
  140. //ll n, m, k, l, r, x, y, z;
  141. //string s, t;
  142. //const ll mod = 1000000007;
  143.  
  144. #define Multitests 1
  145.  
  146. //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  147. //std::mt19937 mt(seed);
  148.  
  149. //int myrand(int mod) {
  150. //return mt()%mod;
  151. //}
  152.  
  153. // Globally declared
  154. vector<vector<int>> seg;
  155.  
  156. // This function mergers two sorted arrays
  157. vector<int> merge(vector<int> &a1, vector<int> &a2)
  158. {
  159. int n = a1.size(), m = a2.size();
  160. int i = 0, j = 0;
  161. vector<int> res;
  162. while (i < n and j < m)
  163. {
  164. if (a1[i] < a2[j])
  165. {
  166. res.push_back(a1[i]);
  167. i += 1;
  168. }
  169. else
  170. {
  171. res.push_back(a2[j]);
  172. j += 1;
  173. }
  174. }
  175. while (i < n)
  176. {
  177. res.push_back(a1[i++]);
  178. }
  179. while (j < m)
  180. {
  181. res.push_back(a2[j++]);
  182. }
  183. return res;
  184. }
  185.  
  186. // This function builds the segment tree
  187. void buildST(int idx, int low, int high, vector<int> &input)
  188. {
  189.  
  190. // Base case: when there is a single elment in the range [LOW, HIGH]
  191. if (low == high)
  192. {
  193. seg[idx].push_back({input[low]});
  194. return;
  195. }
  196. int mid = (low + high) / 2;
  197.  
  198. // Recursive calls to build the left and right subtrees
  199. buildST(2 * idx + 1, low, mid, input);
  200. buildST(2 * idx + 2, mid + 1, high, input);
  201.  
  202. /*
  203. The current node's value is calculated by merging
  204. the values of the left and the right nodes.
  205. */
  206. seg[idx] = merge(seg[2 * idx + 1], seg[2 * idx + 2]);
  207. }
  208.  
  209. int queryHelper(int idx, int l, int r, int low, int high,int k)
  210. {
  211.  
  212. // When a node is completely inside
  213. if (low >= l and high <= r)
  214. {
  215. return int(upper_bound(all(seg[idx]),k) - seg[idx].begin());
  216. }
  217.  
  218.  
  219. // When a node is completely outside
  220. if (r < low or l > high)
  221. {
  222. return 0;
  223. }
  224.  
  225. int mid = (low + high) / 2;
  226.  
  227. /*
  228. Fetch sorted subarray from the left and the right subtrees
  229. and merge them to get a sorted array in the range [l, r]
  230. */
  231. int left = queryHelper(2 * idx + 1, l, r, low, mid,k);
  232. int right = queryHelper(2 * idx + 2, l, r, mid + 1, high,k);
  233. return left + right;
  234. }
  235.  
  236. int query(int l, int r, int k, int n)
  237. {
  238. return queryHelper(0, l, r, 0, n - 1,k);
  239. }
  240.  
  241. using v_t = int;
  242. using vv_t = int64_t;
  243.  
  244. template<v_t MOD> struct modnum {
  245. static_assert(std::numeric_limits<v_t>::max() / 2 >= MOD, "Addition overflows v_t");
  246. static_assert(std::numeric_limits<vv_t>::max() / MOD >= MOD, "Multiplication overflows vv_t");
  247.  
  248. v_t v;
  249. modnum() : v(0) {}
  250. modnum(vv_t _v) : v(v_t(_v % MOD)) { if (v < 0) v += MOD; }
  251. explicit operator v_t() const { return v; }
  252. friend std::istream& operator >> (std::istream& i, modnum& n) { vv_t w; i >> w; n = modnum(w); return i; }
  253. friend std::ostream& operator << (std::ostream& o, const modnum& n) { return o << n.v; }
  254.  
  255. friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  256. friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  257. friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
  258.  
  259. static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
  260. #if !defined(_WIN32) || defined(_WIN64)
  261. return unsigned(x % m);
  262. #endif
  263. // x must be less than 2^32 * m so that x / m fits in a 32-bit integer.
  264. unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
  265. asm("divl %4\n"
  266. : "=a" (quot), "=d" (rem)
  267. : "d" (x_high), "a" (x_low), "r" (m));
  268. return rem;
  269. }
  270.  
  271. modnum& operator += (const modnum& o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
  272. modnum& operator -= (const modnum& o) { v -= o.v; if (v < 0) v += MOD; return *this; }
  273. modnum& operator *= (const modnum& o) { v = fast_mod(vv_t(v) * o.v); return *this; }
  274. modnum operator - () { modnum res; if (v) res.v = MOD - v; return res; }
  275. friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  276. friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  277. friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  278. modnum& operator ++ () { return *this += 1; }
  279. modnum& operator -- () { return *this -= 1; }
  280. modnum operator ++ (int) { auto old = *this; operator++(); return old; }
  281. modnum operator -- (int) { auto old = *this; operator--(); return old; }
  282.  
  283. modnum pow(vv_t e) const {
  284. if (e < 0) return 1 / this->pow(-e);
  285. if (e == 0) return 1;
  286. if (e & 1) return *this * this->pow(e-1);
  287. return (*this * *this).pow(e/2);
  288. }
  289.  
  290. modnum inv() const {
  291. v_t g = MOD, x = 0, y = 1;
  292. for (v_t r = v; r != 0; ) {
  293. v_t q = g / r;
  294. g %= r; std::swap(g, r);
  295. x -= q * y; std::swap(x, y);
  296. }
  297.  
  298. assert(g == 1);
  299. assert(y == MOD || y == -MOD);
  300. return x < 0 ? x + MOD : x;
  301. }
  302. modnum& operator /= (const modnum& o) { return (*this) *= o.inv(); }
  303. friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= modnum(b); }
  304.  
  305. static constexpr v_t modulus() { return MOD; }
  306.  
  307. static constexpr v_t totient() {
  308. v_t tot = MOD, tmp = MOD;
  309. for (v_t p = 2; p * p <= tmp; p++) if (tmp % p == 0) {
  310. tot = tot / p * (p - 1);
  311. while (tmp % p == 0) tmp /= p;
  312. }
  313. if (tmp > 1) tot = tot / tmp * (tmp - 1);
  314. return tot;
  315. }
  316.  
  317. static v_t primitive_root() {
  318. if (MOD == 1) return 0;
  319. if (MOD == 2) return 1;
  320.  
  321. v_t tot = totient(), tmp = tot;
  322. std::vector<int> tot_pr;
  323. for (v_t p = 2; p * p <= tmp; p++) if (tot % p == 0) {
  324. tot_pr.push_back(p);
  325. while (tmp % p == 0) tmp /= p;
  326. }
  327. if (tmp > 1) tot_pr.push_back(tmp);
  328.  
  329. for (v_t r = 2; r < MOD; r++) if (std::gcd(r, MOD) == 1) {
  330. bool root = true;
  331. for (v_t p : tot_pr) root &= modnum(r).pow(tot / p) != 1;
  332. if (root) return r;
  333. }
  334. assert(false);
  335. }
  336.  
  337. static modnum generator() { static modnum g = primitive_root(); return g; }
  338. static v_t discrete_log(modnum v) {
  339. static const v_t M = ceil(std::sqrt(MOD));
  340. static std::unordered_map<v_t, v_t> table;
  341. if (table.empty()) {
  342. modnum e = 1;
  343. for (v_t i = 0; i < M; i++) { table[e.v] = i; e *= generator(); }
  344. }
  345. static modnum f = generator().pow(totient() - M);
  346.  
  347. for (v_t i = 0; i < M; i++) {
  348. if (table.count(v.v)) return table[v.v] + i * M;
  349. v *= f;
  350. }
  351. assert(false);
  352. }
  353.  
  354. static modnum unity_root(int deg) {
  355. assert(totient() % deg == 0);
  356. return generator().pow(totient() / deg);
  357. }
  358.  
  359. static modnum unity_root(int deg, int pow) {
  360. static std::vector<modnum> table{ 0, 1 };
  361. while (int(table.size()) <= deg) {
  362. modnum w = unity_root(int(table.size()));
  363. for (int s = int(table.size()), i = s / 2; i < s; i++) {
  364. table.push_back(table[i]);
  365. table.push_back(table[i] * w);
  366. }
  367. }
  368. return table[deg + (pow < 0 ? deg + pow : pow)];
  369. }
  370.  
  371. static modnum factorial(int n) {
  372. static std::vector<modnum> fact = {1};
  373. assert(n >= 0);
  374. if (int(fact.size()) <= n) {
  375. int had = fact.size();
  376. fact.resize(n + 1);
  377. for (int i = had; i <= n; i++) fact[i] = fact[i-1] * i;
  378. }
  379. return fact[n];
  380. }
  381. static modnum inverse_factorial(int n) {
  382. static std::vector<modnum> finv = {1};
  383. assert(n >= 0);
  384. if (int(finv.size()) <= n) {
  385. int had = finv.size();
  386. finv.resize(n + 1), finv[n] = factorial(n).inv();
  387. for (int i = n - 1; i >= had; i--) finv[i] = finv[i+1] * (i+1);
  388. }
  389. return finv[n];
  390. }
  391.  
  392. static modnum small_inv(int n) {
  393. assert(n > 0); return factorial(n - 1) * inverse_factorial(n);
  394. }
  395.  
  396. static modnum ncr(int n, int r) {
  397. if (r < 0 || n < r) return 0;
  398. return factorial(n) * inverse_factorial(r) * inverse_factorial(n - r);
  399. }
  400. };
  401.  
  402. using mn = modnum<int(1e9 + 7)>;
  403.  
  404. void solve(){
  405. ll n;
  406. cin >> n;
  407. vector<int> arr(n);
  408. fo(i,n) cin >> arr[i];
  409.  
  410. // Setting up globals
  411. seg.clear();
  412. seg.resize(4 * n);
  413.  
  414. // Building the segment tree
  415. buildST(0, 0, n - 1, arr);
  416.  
  417. ll q;
  418. cin >> q;
  419. fo(i,q){
  420. int l,r,x;
  421. cin >> l >> r >> x;
  422. l--; r--;
  423. int y = query(l ,r, x, n);
  424. mn ans = mn::factorial(r - l + 1);
  425. ans /= mn::factorial(y);
  426. ans /= mn::factorial(r - l + 1 - y);
  427. //ps(y);
  428. ps(ans);
  429. }
  430. }
  431.  
  432.  
  433. int32_t main(){
  434. //sieve();
  435. setIO();
  436. #if Multitests
  437. int t; cin >> t;
  438. for(int i = 0; i < t; i++){
  439. #if GOOGLE
  440. cout<<"Case #"<<i + 1<<": ";
  441. #endif
  442. solve();
  443. }
  444. #else
  445. solve();
  446. #endif
  447. return 0;
  448. }
  449.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!