HelloWorld

发表于

苟利国家生死以，
蛤蛤蛤蛤蛤蛤蛤。
蛤蛤蛤蛤蛤蛤蛤，
黑框眼镜裤腰带。

$$ 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
#pragma GCC optimize(3)
#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 Read(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;
}
0%