题解：P12523 [Aboi Round 1] Nomad

chenxumin1017 · 2025-06-02 19:22:45 · 题解

不需要 BSGS 等科技的方法来了。

思路

修改

令 b_i = a_i + 1,\ b_i' = b_{i}^{2} 则 a_i' = f(a_i) = a_i(a_i + 2) = (a_i + 1) ^ 2 - 1 = b_i ^ 2 - 1 = b_i' - 1。

查询

令 F(a_1, a_2, a_3 \cdots a_n) 为 a_1, a_2, a_3 \cdots a_n 的所有非空子序列的元素之积的和。

\begin{aligned}F(a_1, a_2, a_3 \cdots a_n) &= a_1 \cdot F(a_2, a_3 \cdots a_n) + F(a_2, a_3 \cdots a_n) + a_1 \\ &= (a_1 + 1)(F(a_1, a_2, a_3 \cdots a_n) + 1) - 1 \\ &= \displaystyle\prod_{i = 1}^{n}(a_i + 1) - 1 \\ &= \displaystyle\prod_{i = 1}^{n}b_i - 1\end{aligned}

根据以上推导，我们不用维护 a_i，只用维护 b_i 并支持区间 2^k 次方和区间查询乘积，直接线段树维护即可。

时间 O(n \log n \log V)，空间 O(n)。

卡常

然后我们写完代码，并获得了 70 分的高分！

int POW(long long x, int y){
  x %= MOD;
  long long sum = 1;
  for(; y; y >>= 1, x = x * x % MOD){
    if(y & 1)sum = sum * x % MOD;
  }
  return sum;
}
int POW2(long long x, int y){
  x %= MOD2;
  long long sum = 1;
  for(; y; y >>= 1, x = x * x % MOD2){
    if(y & 1)sum = sum * x % MOD2;
  }
  return sum;
}
void build(int l, int r, int id){
  lazy[id] = 1;
  if(l == r){
    tr[id] = a[l] + 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, id * 2);
  build(mid + 1, r, id * 2 + 1);
  tr[id] = tr[id * 2] * 1ll * tr[id * 2 + 1] % MOD;
}
void pushdown(int id){
  if(lazy[id] == 1)return;
  tr[id * 2] = POW(tr[id * 2], lazy[id]);
  tr[id * 2 + 1] = POW(tr[id * 2 + 1], lazy[id]);
  lazy[id * 2] = lazy[id * 2] * 1ll * lazy[id] % MOD2;
  lazy[id * 2 + 1] = lazy[id * 2 + 1] * 1ll * lazy[id] % MOD2;
  lazy[id] = 1;
}
void modify(int l, int r, int id){
  if(l >= pl && r <= pr){
    lazy[id] = lazy[id] * 1ll * k % MOD2;
    tr[id] = POW(tr[id], k);
    return;
  }
  const int mid = (l + r) >> 1;
  pushdown(id);
  if(pl <= mid)modify(l, mid, id << 1);
  if(pr > mid)modify(mid + 1, r, (id << 1) | 1);
  tr[id] = tr[id << 1] * 1ll * tr[(id << 1) | 1] % MOD;
}
int query(int l, int r, int id){
  if(l > pr || r < pl)return 1;
  if(l >= pl && r <= pr)return tr[id];
  pushdown(id);
  return query(l, (l + r) >> 1, id << 1) * 1ll * query(((l + r) >> 1) + 1, r, (id << 1) | 1) % MOD;
}

我们发现懒标记下传常数太大，考虑改成永久化标记。

int POW(int x, int y){
  x %= MOD;
  int sum = 1;
  for(; y; y >>= 1, x = x * x % MOD){
    if(y & 1)sum = sum * x % MOD;
  }
  return sum;
}
int POW2(int x, int y){
  x %= MOD2;
  int sum = 1;
  for(; y; y >>= 1, x = x * x % MOD2){
    if(y & 1)sum = sum * x % MOD2;
  }
  return sum;
}
void build(int l, int r, int id){
  lazy[id] = 1;
  if(l == r){
    tr[id] = a[l] + 1;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, id * 2);
  build(mid + 1, r, id * 2 + 1);
  tr[id] = tr[id * 2] * tr[id * 2 + 1] % MOD;
}
void modify(int l, int r, int id, int pl, int pr, int x){
  if(l > pr || r < pl)return;
  if(l >= pl && r <= pr){
    lazy[id] = lazy[id] * x % MOD2;
    tr[id] = POW(tr[id], x);
    return;
  }
  int mid = (l + r) >> 1;
  modify(l, mid, id * 2, pl, pr, x);
  modify(mid + 1, r, id * 2 + 1, pl, pr, x);
  tr[id] = POW(tr[id * 2] * tr[id * 2 + 1], lazy[id]);
}
int query(int l, int r, int id, int pl, int pr){
  if(l > pr || r < pl)return 1;
  if(l >= pl && r <= pr)return tr[id];
  int mid = (l + r) >> 1;
  return POW(query(l, mid, id * 2, pl, pr) * query(mid + 1, r, id * 2 + 1, pl, pr), lazy[id]);
}

写完之后发现还是 70 分，难道我们就要止步于此了吗？

不，我们还可以卡常。

尽量不要使用 long\ long。
将乘二、除二改为左移、右移。
使用 C++14 (GCC 9) O2 提交。

然后我们就可以借助评测机波动通过了。