苟利国家生死以,
蛤蛤蛤蛤蛤蛤蛤。
蛤蛤蛤蛤蛤蛤蛤,
黑框眼镜裤腰带。
$$ C_{b}^{a}pmod p= C_{b/p}^{a/p}*C_{b pmod p}^{a pmod p}pmod p $$
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
|
#include <cmath> #include <bitset> #include <cstdio> #include <algorithm> const int maxN = 100000; std :: bitset<maxN + 10> c, d; int totc[maxN + 10], totd[maxN + 10]; bool ans[maxN + 10]; int n, q, a[maxN + 10], nowl, nowr, blockSz; inline void (int &x) { x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } struct Query { int op, l, r, v, id; inline bool operator < (const Query &t) const { if (l / blockSz != t.l / blockSz) return l < t.l; else return r < t.r; } }ask[maxN + 10]; inline void Add(int p) { c[a[p]] = ++totc[a[p]]; d[maxN - a[p]] = ++totd[maxN - a[p]]; } inline void Del(int p) { c[a[p]] = --totc[a[p]]; d[maxN - a[p]] = --totd[maxN - a[p]]; } int main() { Read(n); Read(q); blockSz = sqrt(n); for (register int i = 1; i <= n; ++i) Read(a[i]); for (register int i = 1; i <= q; ++i) { Read(ask[i].op); Read(ask[i].l); Read(ask[i].r); Read(ask[i].v); ask[i].id = i; } std :: sort(ask + 1, ask + q + 1); Add(nowl = nowr = 1); for (register int i = 1; i <= q; ++i) { while (nowl > ask[i].l) Add(--nowl); while (nowl < ask[i].l) Del(nowl++); while (nowr < ask[i].r) Add(++nowr); while (nowr > ask[i].r) Del(nowr--); if (ask[i].op == 1) ans[ask[i].id] = (c & (c >> ask[i].v)).any(); else if (ask[i].op == 2) ans[ask[i].id] = (c & (d >> maxN - ask[i].v)).any(); else for (register int j = 1; j * j <= ask[i].v; ++j) if (ask[i].v % j == 0 && c[j] && c[ask[i].v / j]) { ans[ask[i].id] = 1; break; } } for (register int i = 1; i <= q; ++i) puts(ans[i] ? "hana" : "bi"); return 0; }
|
近期评论