Znzryb's Blog
0%

Posted on Edited on

一般来说，一个线段树只应该有一个 merge 函数，因为我们的 merge 是 static 的，我们的逻辑也是用 merge 从子节点中完全重新推出父节点。

2026 杭电春季联赛 3——1009-时空回溯（向下取整除法的性质）

由于我们的 merge 是一个 static 的函数，不会默认保留原来的一些属性，一切都是完全重新推导的。

image

Posted on Edited on

题目大意

题目描述

给定一个长度为 nn 的数组 AA 以及一个阈值 mm。你需要维护这个数组并支持以下两种操作，共执行 QQ 次：

  • 1 L R X：将区间 [L,R][L, R] 内的所有元素减去 XX（即对于 L≤i≤RL \le i \le R，执行 Ai←Ai−XA_i \leftarrow A_i - X）。

  • 2 L R：将区间 [L,R][L, R] 内的所有元素右移一位（相当于除以 22 向下取整，即对于 L≤i≤RL \le i \le R，执行 Ai←⌊Ai2⌋A_i \leftarrow \lfloor \frac{A_i}{2} \rfloor）。

在每一次操作结束后，如果整个数组中存在至少一个元素小于等于阈值 mm，则会触发一次“时空回溯”：

  1. 全局重置次数 kk 的值增加 11。

  2. 整个数组 AA 立即恢复为最开始的初始状态。

要求在处理完所有给定的 QQ 次操作后，输出最终的重置次数 kk（初始时 k=0k=0）。

数据范围

  • 数据组数 T≤10T \le 10。

  • 1≤n,Q≤1051 \le n, Q \le 10^5。

  • 0≤m<2300 \le m < 2^{30}。

  • 初始数组满足 m<Ai<230m < A_i < 2^{30}。

  • 对于操作 1：1≤L≤R≤n1 \le L \le R \le n，0≤X<2300 \le X < 2^{30}。

  • 对于操作 2：1≤L≤R≤n1 \le L \le R \le n。

样例输入

1
2
3
4
5
6
1
3 1 3
5 4 6
1 1 2 4
2 2 3
1 1 3 5

样例输出

1
2

样例解释

初始时数组为 [5,4,6][5, 4, 6]，阈值 m=1m = 1，重置次数 k=0k = 0。

  • 第 11 次操作（1 1 2 4）：对区间 [1,2][1, 2] 的元素减去 44，数组变为 [1,0,6][1, 0, 6]。此时存在元素（11 和 00）小于等于阈值 11，触发回溯。重置次数 k←1k \leftarrow 1，数组重置为初始状态 [5,4,6][5, 4, 6]。

  • 第 22 次操作（2 2 3）：对区间 [2,3][2, 3] 的元素右移一位，数组变为 [5,2,3][5, 2, 3]。此时数组中所有元素均大于 11，不触发回溯。

  • 第 33 次操作（1 1 3 5）：对区间 [1,3][1, 3] 的元素减去 55，数组变为 [0,−3,−2][0, -3, -2]。此时存在元素小于等于阈值 11，触发回溯。重置次数 k←2k \leftarrow 2，数组重置为初始状态 [5,4,6][5, 4, 6]。

所有操作执行完毕，最终的重置次数 kk 为 22。

思路讲解

gemini 的这个数学功底比较好，直接合并了这个位移操作和这个减法操作。

PDF

image

这个向下嵌套性质不是那么容易可以看出来的，那么我让 gemini 写了一个完整的，直观的，而且也是非常严谨的这个解释，还是非常好的：

image

不过我们是用题解的这个做法：

image

我们可以维护一个这个标记数组，

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=17893

心路历程（WA，TLE，MLE……）

PDF

一般来说，一个线段树只应该有一个 merge 函数，因为我们的 merge 是 static 的，我们的逻辑也是用 merge 从子节点中完全重新推出父节点

vector clear() 函数减少内存的重新分配（保留 capacity），进而加快速度

类似于 t.op_ls[i].type，这样子比较复杂的东西，可以使用引用，重命名为 t_op_ls[i].type，这样子书写的时候可以少一层，可以减少写错的可能性

注意特殊操作的范围，不一定就局限在【l，r】了，可能是全局操作【1，N】。

Posted on Edited on

常见错误之除零错误。

https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=17130

image

一般来说，只要除数不是一个简单的，一个变量，都要担心这个除 0 错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void gen_eraly_seg() {
    for (int i = 1; i <= N; ++i) {
        ll early_sz;
        if (i == 1) {
            early_sz = K - (bound_win + K - 1) / K;
        } else {
            if (early_sz_ls[i - 1] - K == 0) {
                early_sz = K;
            } else {
              // 这里这个除法要小心除 0 错误。
                early_sz = (bound_win - K * K) / (early_sz_ls[i - 1] - K);
            }
        }
        early_sz = min(early_sz, K);
        early_sz_ls[i] = early_sz;
        for (int j = 1; j <= early_sz; ++j) {
            ans_mat[i][j] = idx;
        }
        if (early_sz != 0) {
            ++idx;
        }
    }
}

Posted on Edited on

Lucas 定理是怎么来的？

Lucas 定理的最直观证明是通过生成函数（母函数）和二项式定理来推导的。

首先，根据二项式定理，我们知道组合数 CnmC_n^m 其实就是多项式 (1+x)n(1+x)^n 展开后 xmx^m 这一项的系数。

对于任意质数 pp，考虑 (1+x)p(modp)(1+x)^p \pmod p 的展开式：

(1+x)p=Cp0x0+Cp1x1+Cp2x2+⋯+Cppxp(1+x)^p = C_p^0 x^0 + C_p^1 x^1 + C_p^2 x^2 + \dots + C_p^p x^p

因为 pp 是质数，当 1≤i≤p−11 \le i \le p-1 时，Cpi=p!i!(p−i)!C_p^i = \frac{p!}{i!(p-i)!} 的分子里有一个 pp，而分母里没有 pp 可以把它约掉。所以中间所有的项都是 pp 的倍数，在模 pp 意义下全部等于 00。
因此我们得到了一个非常漂亮的核心结论：

(1+x)p≡1+xp(modp)(1+x)^p \equiv 1 + x^p \pmod p

现在我们来求 (1+x)n(modp)(1+x)^n \pmod p 中 xmx^m 的系数。
我们将 nn 和 mm 拆分成除以 pp 的商和余数（类似于把它们转成 pp 进制）：
令 n=⌊n/p⌋×p+(n mod p)n = \lfloor n/p \rfloor \times p + (n \bmod p)
令 m=⌊m/p⌋×p+(m mod p)m = \lfloor m/p \rfloor \times p + (m \bmod p)

代入多项式中：

由于前面证明的核心结论，把内部的 (1+x)p(1+x)^p 替换掉：

(1+x)n=(1+x)⌊n/p⌋×p+(n mod p)=((1+x)p)⌊n/p⌋×(1+x)n mod p \begin{aligned}(1+x)^n &= (1+x)^{\lfloor n/p \rfloor \times p + (n \bmod p)} \\&= \left( (1+x)^p \right)^{\lfloor n/p \rfloor} \times (1+x)^{n \bmod p} \\\end{aligned}

(1+x)n≡(1+xp)⌊n/p⌋×(1+x)n mod p(modp) \begin{aligned}(1+x)^n &\equiv (1+x^p)^{\lfloor n/p \rfloor} \times (1+x)^{n \bmod p} \pmod p\end{aligned}

我们要求的是 xmx^m 的系数，而 xm=(xp)⌊m/p⌋×xm mod px^m = (x^p)^{\lfloor m/p \rfloor} \times x^{m \bmod p}。
所以在右边这两个括号相乘时，我们必须：

  1. 从前一个括号 (1+xp)⌊n/p⌋(1+x^p)^{\lfloor n/p \rfloor} 中选出 (xp)⌊m/p⌋(x^p)^{\lfloor m/p \rfloor}，这部分的系数是 C⌊n/p⌋⌊m/p⌋C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}。

  2. 从后一个括号 (1+x)n mod p(1+x)^{n \bmod p} 中选出 xm mod px^{m \bmod p}，这部分的系数是 Cn mod pm mod pC_{n \bmod p}^{m \bmod p}。

两者相乘，就得到了 xmx^m 的总系数。这就是 Lucas 定理的来源：

Cnm≡C⌊n/p⌋⌊m/p⌋×Cn mod pm mod p(modp)C_{n}^{m} \equiv C_{\lfloor n / p \rfloor}^{\lfloor m / p \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p

关于这道 AcWing 题目与你的模板

注意观察这道题目的输入格式：每一组询问都会给出一个不同的质数 pp！

我们刚才在你的 main.tex 里，把 Lucas 定理改成了复用你已有的 Comb 命名空间和全局的 mod。那个模板只适用于所有询问的模数 pp 固定不变的情况（因为我们需要针对固定的 mod 预处理阶乘）。

对于这道题，因为 pp 会变（最高到 10510^5），所以我们不能用全局预处理，反而应该用我们刚才撤掉的那份按定义暴力算的代码！因为暴力算单次是 O(p)O(p) 的，加上 Lucas 递归，总时间大概是 O(plog⁡pn)O(p \log_p n)，这道题 n≤20n \le 20 组询问，最大运算量在 2×1062 \times 10^6 左右，完全可以光速通过。

以下是可以直接通过这道题的 AC 代码，风格和我们刚才讨论的完全一致：

AC

https://www.acwing.com/problem/content/submission/code_detail/44735227/

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
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

ll mod;

// 你的组合数模板
namespace Comb{    
  vector<ll> frac, infrac;
  int ln = 1;
  bool initialized = false;

  inline ll binpow(ll a, ll k) {
    ll res = 1;
    a %= mod;
    while (k > 0) {
      if (k & 1) res = (res * a) % mod;
      a = (a * a) % mod;
      k >>= 1;
    }
    return res;
  }

  void Comb(int n) {
    ln = n;
    frac.assign(n + 5, 1);
    infrac.assign(n + 5, 1);
    for (int i = 1; i <= ln; ++i) {
      frac[i] = (frac[i - 1] * i) % mod;
    }
    infrac[ln] = binpow(frac[ln], mod - 2);
    for (int i = ln - 1; i >= 0; --i) {
      infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
    }
  }

  inline ll CC(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    if(!initialized){
      // 【核心细节】：Lucas定理的余数最大为 mod-1，所以只用预处理到 mod-1。
      // 绝对不能预处理到 mod，否则 frac[mod] = 0，会导致所有的 infrac 变成 0。
      Comb(mod - 1); 
      initialized = true;
    }
    ll res = frac[n];
    res = (res * infrac[n - k]) % mod;
    res = (res * infrac[k]) % mod;
    return res;
  }
}
using namespace Comb;

// Lucas 定理递归求解，复用 CC 模板
inline ll lucas(ll a, ll b) {
  if (a < mod && b < mod) return CC(a, b);
  return CC(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}

void solve() {
  ll a, b;
  cin >> a >> b >> mod;
  
  // 每次 mod 发生变化，必须重置初始化标记
  initialized = false; 
  
  cout << lucas(a, b) << '\n';
}

int main() {
  // 优化输入输出
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n;
  if (cin >> n) {
    while (n--) {
      solve();
    }
  }
  return 0;
}