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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
| struct LPow { static const int B = 32768; int sk[B], bk[B], Mod; LPow() : Mod(1) {} void init(int _Mod) { Mod = _Mod; sk[0] = bk[0] = 1; for (int i = 1; i < B; ++ i) sk[i] = (LL) sk[i - 1] * c % Mod; bk[1] = (LL) sk[B - 1] * c % Mod; for (int i = 2; i < B; ++ i) bk[i] = (LL) bk[i - 1] * bk[1] % Mod; } int lpow(int x) { return bk[x >> 15] * (LL) sk[x & (B - 1)] % Mod; } } lp[70];
int phi(int n) { int res = n; for (int i = 2; i <= n / i; ++ i) if (n % i == 0) { res /= i, res *= (i - 1); while (n % i == 0) n /= i; } if (n ^ 1) res /= n, res *= (n - 1); return res; }
struct Node { int l, r, cnt, sum; } tr[N << 2];
void pushup(int x) { adj(tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum - Mod); tr[x].cnt = std::min(tr[x << 1].cnt, tr[x << 1 | 1].cnt); }
void build(int x, int l, int r) { tr[x] = {l, r, 0, a[l]}; if (l == r) return; int mid = (l + r) >> 1; build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r); pushup(x); }
void modify(int x, int l, int r) { if (tr[x].cnt > lim || tr[x].l > r || tr[x].r < l) return; if (tr[x].l == tr[x].r) { tr[x].cnt ++; int cur = a[tr[x].l]; bool flag = false; for (int i = tr[x].cnt; i; -- i) { int tmp = cur; LL res = 1; while (tmp -- && !flag) { res *= c; if (res >= lp[i].Mod) { flag = true; break; } } cur = lp[i].lpow(cur); if (flag || lp[i].Mod == 1) cur += lp[i].Mod; } tr[x].sum = cur % Mod; return; } modify(x << 1, l, r), modify(x << 1 | 1, l, r); pushup(x); }
int query(int x, int l, int r) { if (tr[x].l > r || tr[x].r < l) return 0; if (tr[x].l >= l && tr[x].r <= r) return tr[x].sum; int tmp; return adj(tmp = query(x << 1, l, r) + query(x << 1 | 1, l, r) - Mod); }
|
Related Issues not found
Please contact @mydcwfy to initialize the comment