[LibreOJ 2142][SHOI2017]相逢是问候

danihao123 posted @ 2018年3月06日 16:45 in 题解 with tags 线段树 loj 联考 欧拉降幂公式 , 2629 阅读
转载请注明出处:http://danihao123.is-programmer.com/

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;
}
RBSE 7th Class Text 说:
Jul 15, 2023 07:27:44 PM

Rajasthan High School Every Year Academic Year Close in Month of April, Haryana , Rajasthan High School Academic Year Start in Month of Jun, So Rajasthan Board 6th Class new Students Can Download English, Hindi, Medium Subject Books Chapter wise and Full Textbooks Pdf is Available in Online Mode,Rajasthan 7th Textbook 2024 Should be Followed as the Prime Resource Throughout the year to Clear RBSE 7th Class Textbook 2024 All Doubts and Strengthen your knowledge. RBSE 7th Textbook 2024 Provides an easy Explanation for Various Concepts in the Curriculum. Our Portal are Providing the Latest Verition of Rajasthan VII Book 2024 which is Published by the Rajasthan State Textbook Board. All the Chapters can be Downloaded in the form of PDFs.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter