[LibreOJ 2142][SHOI2017]相逢是问候
f**********ck我终于肝掉这道题了……在这种辣鸡题上浪费了大量时间
首先一堆\(c\)套起来的幂让我们想到了上帝与集合的正确用法那道题(这题题解我屯到现在没写,还是算了吧就写这题得了)……那让我们试试欧拉降幂公式?
观察欧拉降幂公式
\[a^x\equiv a^{x\mod \varphi(m) + \varphi(m)}\pmod{m}(a\geq m)\]
在多次降幂之后,最后肯定存在一个膜数为1,最后在对这一个地方进行操作的话,虽然\(A[i]\)的位置会被移到更高的次幂上,但是开始出现膜数1的地方一定只能取到1了,所以再对这些地方操作是不合理的。
每次取\(\varphi(x)\)都会使数至少下降一半,所以一个数最多被操作\(\log_2 p\)次。
然后我就跪了(虽然在BZOJ上水过去了),后来手肝gprof发现瓶颈在快速幂(逃
然后这TM怎么优化……膜了一发题解发现正解非常的KBS……
对于一个幂,他的指数肯定可以表示为\(2^{16} a + b\)且\(a\)最大的形式……然后我们可能用到的膜数是很少的,对于每种膜数大力预处理可能的\(b\)的答案和\(a\)的答案,然后求一次幂就\(O(1)\)了……
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <cmath> #include <algorithm> #include <utility> #include <climits> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> const int maxn = 50005; const int maxno = maxn << 2; const int siz = 65536; typedef long long ll; inline ll phi(ll x) { ll bd = sqrt(x + 0.5); ll ans = x; for(ll i = 2; i <= bd; i ++) { if(x % i == 0LL) { ans = ans / i * (i - 1LL); while(x % i == 0LL) { x /= i; } } } if(x > 1LL) ans = ans / x * (x - 1LL); return ans; } int n, m; ll p, c; ll f[100]; int fn, bd; ll pow1[70][siz], pow2[70][siz]; inline void process() { f[0] = p; fn = 1LL; for(int i = 1; ; i ++) { f[i] = phi(f[i - 1]); if(f[i] == 1LL) { fn = i; break; } } ll tmp = 1LL; bd = 0; if(c != 1LL) { while(tmp * c < p) { bd ++; tmp *= c; } } else { bd = 0x7fffffff; } f[69] = LLONG_MAX; for(int i = 0; i <= fn; i ++) { ll c1 = c % f[i]; ll c2 = c1; int t = 16; while(t --) c2 = (c2 * c2) % f[i]; pow1[i][0] = 1LL; if(i == fn) pow1[i][0] = 0; for(int j = 1; j < siz; j ++) pow1[i][j] = (pow1[i][j - 1] * c1) % f[i]; pow2[i][0] = 1LL; if(i == fn) pow2[i][0] = 0; for(int j = 1; j < siz; j ++) pow2[i][j] = (pow2[i][j - 1] * c2) % f[i]; } int i = 69; for(int g = 0; g <= 0; g ++) { ll c1 = c % f[i]; ll c2 = c1; int t = 16; while(t --) c2 = (c2 * c2) % f[i]; pow1[i][0] = 1LL; for(int j = 1; j < siz; j ++) pow1[i][j] = (pow1[i][j - 1] * c1) % f[i]; pow2[i][0] = 1LL; for(int j = 1; j < siz; j ++) pow2[i][j] = (pow2[i][j - 1] * c2) % f[i]; } } inline ll pow_mod(ll a, ll b, ll p) { return (pow1[p][b & (siz - 1)] * pow2[p][b >> 16]) % f[p]; } ll A[maxn]; int be_done[maxn]; ll sumv[maxno]; bool break_down[maxno]; inline void maintain(int o) { int lc = o << 1, rc = o << 1 | 1; sumv[o] = (sumv[lc] + sumv[rc]); if(sumv[o] >= p) sumv[o] -= p; break_down[o] = (break_down[lc] && break_down[rc]); } inline ll get_ans(int i) { register ll up; for(int j = be_done[i]; j >= 0; j --) { if(j == be_done[i]) { up = A[i]; } else { if(up > bd) { up = pow_mod(c % f[j], up, j) + f[j]; } else { up = pow_mod(c, up, 69); } } } return up; } void build_tree(int o, int L, int R) { if(L == R) { be_done[L] = 0; break_down[o] = 0; sumv[o] = A[L]; } else { int M = (L + R) / 2; build_tree(o << 1, L, M); build_tree(o << 1 | 1, M + 1, R); maintain(o); } } int ql, qr; void modify(int o, int L, int R) { if(L == R) { be_done[L] ++; if(c == 1LL) { sumv[o] = 1LL; break_down[o] = true; } else { sumv[o] = get_ans(L) % p; if((A[L] != 0LL && be_done[L] == fn) || (A[L] == 0LL && be_done[L] == fn + 1)) break_down[o] = true; } } else { int M = (L + R) / 2; if(ql <= M && !break_down[o << 1]) { modify(o << 1, L, M); } if(qr > M && !break_down[o << 1 | 1]) { modify(o << 1 | 1, M + 1, R); } maintain(o); } } ll query(int o, int L, int R) { if(ql <= L && R <= qr) { return sumv[o]; } else { int M = (L + R) / 2; ll ans = 0; if(ql <= M) { ans = (ans + query(o << 1, L, M)); if(ans >= p) ans -= p; } if(qr > M) { ans = (ans + query(o << 1 | 1, M + 1, R)); if(ans >= p) ans -= p; } return ans; } } int main() { // freopen("17.in", "r", stdin); // freopen("dummy", "w", stdout); scanf("%d%d%lld%lld", &n, &m, &p, &c); process(); for(int i = 1; i <= n; i ++) scanf("%lld", &A[i]); build_tree(1, 1, n); while(m --) { int op; scanf("%d%d%d", &op, &ql, &qr); if(op == 0) { modify(1, 1, n); } else { printf("%lld\n", query(1, 1, n)); // fflush(stdout); } } return 0; }