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;
}

• 相关文章
• 全局相关文章