专栏文章

焚诀

AA1ex_5yn7ax
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimxg8i9
此快照首次捕获于
2025/12/01 17:08
3 个月前
此快照最后确认于
2025/12/01 17:08
3 个月前
查看原文

数论部分

组合计数

小球模型

以下假定 n 个小球，m 个盒子
小球之间没有区别，盒子之间没区别，盒子不能为空：
dpi,jdp_{i,j} 表示前 j 个盒子放 i 个球
dpi,j=dpi−1,j−1+dpi−j,jdp_{i,j}=dp_{i-1,j-1}+dp_{i-j,j}
有点难理解 但
C
-
--
----
-----
每次都是加一条横线
小球之间没有区别，盒子之间没区别，盒子能为空：
把上面的 dpn,idp_{n,i} 累加起来即可
小球之间没有区别，盒子之间有区别，盒子不能为空：
插板法，在 n-1 个空隙里放 m-1 个板子 答案为 Cn−1m−1C_{n-1}^{m-1}
小球之间没有区别，盒子之间有区别，盒子为空：
先加 m 个小球，继续插板，有 Cn+m−1n−1C_{n+m-1}^{n-1} 种插法，最后拿掉加的 m 个就和原题等价了
小球之间有区别，盒子之间没有区别，盒子不能为空：
dpi,jdp_{i,j} 意为前 i 个盒子放 j 个球
dpi,j=dpi−1,j−1+dpi,j−1∗idp_{i,j}=dp_{i-1,j-1}+dp_{i,j-1}*i
小球之间有区别，盒子之间没有区别，盒子能为空：
把上面的 dpi,ndp_{i,n} 累加起来即可
小球之间有区别，盒子之间有区别，盒子不能为空：
dpi,jdp_{i,j} 意为前 i 个盒子放 j 个球
dpi,j=dpi−1,j−1×(m−i+1)+dpi,j−1∗idp_{i,j}=dp_{i-1,j-1} \times (m-i+1)+dp_{i,j-1}*i
小球之间有区别，盒子之间有区别，盒子能为空：
每个小球都有 m 个选择，直接就是 mnm^n

二项式反演

即广义容斥原理
** 反演：简而言之为两种函数之间的变换关系 **
二项式反演：
形式 1：
gng_n 表示至多 n 个 / 种 方案数，fnf_n 表示恰好 n 个 / 种 方案数
gn=∑i=0nfig_{n}=\sum_{i=0}^{n}f_{i}
fn=∑i=0n(−1)n−iCnigif_{n}=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}g_{i}
形式 2：
gkg_k 表示至少 k 个 / 种 方案数，fkf_k 表示恰好 k 个 / 种 方案数
gk=∑i=knCikfig_{k}=\sum_{i=k}^{n} C_{i}^{k}f_{i}
fk=∑i=kn(−1)i−kCikgif_{k}=\sum_{i=k}^{n} (-1)^{i-k} C_{i}^{k}g_{i}

数论函数

常见数论（积性）函数：
  • ** 单位函数 **ε(n)=[n=1]\varepsilon (n)=[n=1]
  • 常数函数 1(n)=1\mathbb{1}(n)=1
  • 恒等函数 idk(n)=nk\text{id}_k(n)=n^k
    id0\text{id}_0 常省略下标写作 id\text{id}。
  • 除数函数 σk(n)=∑d∣ndk\sigma_k(n)=\sum_{d\mid n}d^k
    特殊的，σ0(n)\sigma_0(n) 习惯称为 d(n)d(n)，σ1(n)\sigma_1(n) 常省略下标写作 σ(n)\sigma(n)。

数论分块

将一个区间分成 n\sqrt n 块，每块的 ⌊ni⌋\lfloor\frac ni\rfloor 相同，做到 O(n)\mathcal O(\sqrt n) 求出 ⌊ni⌋\lfloor\frac ni\rfloor 的前缀和。例如
∑i=1nd(i)=∑i=1n∑jk[jk=i](最基础的变形)=∑ij[ij≤n]=∑i=1n⌊ni⌋\begin{aligned}\sum^{n}_{i = 1}d(i) &= \sum ^{n}_{i = 1}\sum_{jk}[jk=i] &(最基础的变形)\\&= \sum_{ij}[ij\le n] \\&= \sum^n_{i = 1}\lfloor \frac{n}{i} \rfloor &\\\end{aligned}

exgcd

裴蜀定理：若对于 ax+by=cax+by=c 有 gcd⁡(a,b)∤c\gcd(a,b)\nmid c 则此方程无解
若有解，则先解 ax+by=gcd⁡(a,b)ax+by= \gcd (a,b) 再乘 cgcd⁡(a,b)\frac{c}{\gcd(a,b)}
从 gcd⁡\gcd 着手
若 ax+by=gcd⁡(a,b)ax+by= \gcd (a,b)
递归求解 bx′+(a mod b)y′=gcd⁡(b,a mod b)bx'+(a\text{ mod }b)y'=\gcd(b,a\text{ mod }b)
x={1  (b=0)y′ (others)x=\begin{cases} 1\ \ (b=0)\\y'\ (others)\end{cases}
y={0 (b=0)x′−⌊ab⌋×y′ (others)y=\begin{cases}0\ (b=0)\\x'-\lfloor\frac ab\rfloor\times y'\ (others)\end{cases}
C
void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    int x0,y0;
    exgcd(b,a%b,x0,y0);
    x=y0;
    y=x0-(a/b)*y0;
}

逆元：

若有：
a×b≡1(modp)a\times b\equiv1\pmod p
则称 b 是 a 在模 p 下的逆元，记作 a−1a^{-1}，若 aa, pp 不互质则不存在这样的 a−1a^{-1}。
  • 原式可化为 ab−kp=1ab-kp=1，exgcd⁡ex \gcd 即可
  • 若 pp 是质数，则有 a−1=ap−2a^{-1}=a^{p-2}
  • 线性递推 1∼n!1\sim n! 的逆元有以下式子：
    1(n−1)!≡1n!×n(modp)\frac 1{(n-1)!}\equiv\frac 1{n!}\times n\pmod p
    QED.QED.
    我们 O(log⁡n)\mathcal O(\log n) 计算出 n!n! 的逆元，即可倒推。

CRT

求方程组：
{x≡a1(modb1)x≡a2(modb2)x≡a3(modb3)...x≡an(modbn)\left\{\begin{matrix} x\equiv a_1\pmod{b_1}\\ x\equiv a_2\pmod{b_2}\\ x\equiv a_3\pmod{b_3}\\ ...\\ x\equiv a_n\pmod{b_n}\\ \end{matrix}\right.
的一个可行解（保证 bib_i 互质）。
我们可以发现，我们实际只需考虑这几组方程：
{x1≡a1(modb1)x1≡0(modb2)x1≡0(modb3)...x1≡0(modbn)\left\{\begin{matrix} x_1\equiv a_1\pmod{b_1}\\ x_1\equiv 0\pmod{b_2}\\ x_1\equiv 0\pmod{b_3}\\ ...\\ x_1\equiv 0\pmod{b_n}\\ \end{matrix}\right. {x2≡0(modb1)x2≡a2(modb2)x2≡0(modb3)...x2≡0(modbn)\left\{\begin{matrix} x_2\equiv 0\pmod{b_1}\\ x_2\equiv a_2\pmod{b_2}\\ x_2\equiv 0\pmod{b_3}\\ ...\\ x_2\equiv 0\pmod{b_n}\\ \end{matrix}\right. {x3≡0(modb1)x3≡0(modb2)x3≡a3(modb3)...x3≡0(modbn)\left\{\begin{matrix} x_3\equiv 0\pmod{b_1}\\ x_3\equiv 0\pmod{b_2}\\ x_3\equiv a_3\pmod{b_3}\\ ...\\ x_3\equiv 0\pmod{b_n}\\ \end{matrix}\right. ...\text{...} {xn≡0(modb1)xn≡0(modb2)xn≡0(modb3)...xn≡an(modbn)\left\{\begin{matrix} x_n\equiv 0\pmod{b_1}\\ x_n\equiv 0\pmod{b_2}\\ x_n\equiv 0\pmod{b_3}\\ ...\\ x_n\equiv a_n\pmod{b_n}\\ \end{matrix}\right.
最后我们把所有解合并，∑xi\sum x_i 即为答案（可以思考一下）。
于是我们观察其中一个方程组研究，为了方便，我们取第一个处理，其他同理。
我们发现方程可以进一步化为 {y1≡1(modb1)y1≡0(modb2)y1≡0(modb3)...y1≡0(modbn)\left\{\begin{matrix} y_1\equiv 1\pmod{b_1}\\ y_1\equiv 0\pmod{b_2}\\ y_1\equiv 0\pmod{b_3}\\ ...\\ y_1\equiv 0\pmod{b_n}\\ \end{matrix}\right.，其中 yi×ai=xiy_i\times a_i=x_i。
由于需要保证解能被其他模数整除，我们设 M=∏bi,Mi=MbiM=\prod b_i,M_i=\frac M{b_i}，则我们需要构造 t1t_1 使得 M1×t1≡1(modb1)M_1\times t_1\equiv1\pmod {b_1}。
其实 t1t_1 就是 M1M_1 模 p1p_1 意义下的逆元，于是 x1=a1y1=a1M1t1x_1=a_1y_1=a_1M_1t_1。
于是 x=∑xi=∑aiMitix=\sum x_i=\sum a_iM_it_i。

EXCRT

我们可以将方程化为
{x0=a1−k1b1x0=a2−k2b2⇔a1−k1b1=a2−k2b2⇔k2b2−k1b1=a2−a1\begin{aligned} \left\{\begin{matrix} x_0= a_1-k_1b_1\\ x_0= a_2-k_2b_2\\ \end{matrix}\right. &\Leftrightarrow a_1-k_1b_1=a_2-k_2b_2\\ &\Leftrightarrow k_2b_2-k_1b_1=a_2-a_1 \end{aligned}
注意到这是一个不定方程，我们可以用 \texttt{ex \gcd } 求解，得到一组特解 k1,k2k_1,k_2。
则它们的通解即为
{K1=k1+t×b2gcd⁡(b1,b2)K2=k2+t×b1gcd⁡(b1,b2)\begin{aligned} \left\{\begin{matrix} K_1=k_1+t\times\frac{b_2}{\gcd(b_1,b_2)}\\ K_2=k_2+t\times\frac{b_1}{\gcd(b_1,b_2)} \end{matrix}\right. \end{aligned}
我们代入之前的任意一个方程，得到
x0=a1−K1b1=a1−k1b1−t×b1b2gcd⁡(b1,b2)=a1−k1b1−t×lcm⁡(b1,b2)\begin{aligned} x_0&=a_1-K_1b_1\\ &=a_1-k_1b_1-t\times\frac{b_1b_2}{\gcd(b_1,b_2)}\\ &=a_1-k_1b_1-t\times\operatorname{lcm}(b_1,b_2)\\ \end{aligned}
于是得到
x0≡a1−k1b1(modlcm⁡(b1,b2))x_0\equiv a_1-k_1b_1\pmod{\operatorname{lcm}(b_1,b_2)}
其中 a1,b1a_1,b_1 均已知，k1k_1 已求出，于是我们便成功合并了两个方程。

欧拉函数

定义为 1∼n1\sim n 中与 nn 互质的数的个数。 形式化的说，φ(n)=∑i=1n[gcd⁡(n,i)=1]\varphi(n)=\sum^n_{i=1}[\gcd(n,i)=1]
  • 结论 1：φ(n)=n−1\varphi(n)=n-1，其中 nn 是一个质数。
    证明：显然只有 nn 本身与 nn 不互质。
  • 结论 2：欧拉函数为积性函数，即 φ(nm)=φ(n)φ(m)(\varphi(nm)=\varphi(n)\varphi(m)( 当 n⊥m)n\perp m)。
  • 结论 3：φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1}，其中 pp 是一个质数。
    证明：将 pkp^k 化为 p×pk−1p\times p^{k-1} 可以发现，只有 pp 的前 pk−1p^{k-1} 个倍数与 pkp^k 不互质。
  • 结论 4：利用结论 2 和结论 3，我们可以得到欧拉函数的另一种形式：
φ(n)=n×∏pi−1pi\varphi(n)=n\times \prod\frac{p_i-1}{p_i}
其中 p∈prime,∏piki=np\in \text{prime},\prod p_i^{k_i}=n。
证明：将 nn 化为唯一分解形式，则有
φ(n)=∏φ(piki)=∏piki(1−1pi)=∏piki×∏(1−1pi)=n×∏pi−1pi\begin{aligned} \varphi(n)&=\prod\varphi(p_i^{k_i})\\ &=\prod p_i^{k_i}(1-\frac{1}{p_i})\\ &=\prod p_i^{k_i}\times\prod(1-\frac{1}{p_i})\\ &=n\times\prod\frac{p_i-1}{p_i} \end{aligned}
  • 结论 5：φ(nm)φ(gcd⁡(n,m))=φ(n)φ(m)gcd⁡(n,m)\varphi(nm)\varphi(\gcd(n,m))=\varphi(n)\varphi(m)\gcd(n,m)。
    证明：由上化简可得。
  • 结论 6：n=∑d∣nφ(d)n=\sum_{d\mid n}\varphi(d)。
    证明 1：我们构造一个函数 f(x)=∑1≤d≤n[gcd⁡(n,d)=x]f(x)=\sum_{1\le d\le n}[\gcd(n,d)=x]，则 n=∑i=1nf(i)n=\sum^n_{i=1}f(i)。易知 f(x)=φ(nx)f(x)=\varphi(\frac nx)，则结论 5 成立。
    证明 2：我们有分数 1n,2n,3n,...,nn\frac 1n,\frac 2n,\frac 3n,...,\frac nn，将其中能约分的约分，则对于任意数 d(d≤n)d(d\le n)，分母为 dd 的分数个数为 φ(d)\varphi(d)，则结论 5 成立。
    进一步，我们还可以得到 gcd⁡(a,b)=∑d∣a,d∣bφ(d)=∑d[d∣a][d∣b]φ(d)\gcd(a,b)=\sum_{d\mid a,d\mid b}\varphi(d)=\sum_d[d\mid a][d\mid b]\varphi(d)（这个结论有些地方称之为欧拉反演）。
  • 结论 7：
    φ(n!)={φ((n−1)!)×n,n∉primeφ((n−1)!)×(n−1),n∈prime\varphi(n!)= \begin{aligned} \left\{\begin{matrix} \varphi((n-1)!)\times n,&n\notin\text{prime}\\ \varphi((n-1)!)\times (n-1),&n\in\text{prime}\\ \end{matrix}\right. \end{aligned}
    由结论 4 可得。
    筛 n=n′∗pn=n'*p 时
    若 p⊥n′p\perp n'，可以使用结论 2
    若 p∣n′p\mid n', 说明 n′n' 包含 nn 的所有质因子，所以 φ(n)=p×n′×∏(1−pi−1pi)=p×φ(n′)\varphi(n)=p\times n'\times\prod(1-\frac{p_i-1}{p_i})=p\times\varphi(n')。
    C
    bool vis[N];
int phi[N];
int p[N],tot;
void init(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i]) p[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot && i*p[j]<=n;j++){
            vis[i*p[j]]=true;
            if(i%p[j]==0) {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }else phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
}
    类似地，奇性函数都可筛出来
    μ\mu
    CPP
    void getmu(int n) {
    for(int i=1;i <= n;i++)  mu[i]=1, vis[i];
    for(int i=2;i <= n;i++) {
        if(vis[i])  continue;
        mu[i] = -1;
        for(int j = 2*i; j <= n;j += i) {
            vis[j] = 1;
            if(j % (i*i) == 0)  mu[j] = 0;
            else  mu[j] *= -1;
        }
    }
}

    狄利克雷卷积：

    狄利克雷卷积是是数论函数之间的二元运算，符号为 ∗\ast。
    具体来说，定义两个数论函数 f(x)f(x) 和 g(x)g(x)，定义卷积结果为 h(x)h(x)。
    则：
    h(x)=∑d∣nf(d)g(xd)h(x)=\sum_{d\mid n}f(d)g(\frac xd)
    记为 h=f∗gh=f\ast g。
    狄利克雷卷积遵循交换律、结合律、分配律。
    • 定义 1：若有两数论函数 f,gf,g 满足 f∗g=εf\ast g=\varepsilon，其中 ε\varepsilon 为单位函数，则 gg 为 ff 的逆元，记作 f−1f^{-1}。
    • 结论 1：如果 f,gf,g 为积性函数，则 f∗gf\ast g 也为积性函数。由上易证。
    • 结论 2：如果 ff 为积性函数，则 f−1f^{-1} 也为积性函数。由上易证。
    一些常见的卷积：
    • idk∗1=σk\text{id}_k\ast \mathbb1=\sigma_k
    • φ∗1=id\varphi\ast\mathbb1=\text{id}
    • 1∗1=d\mathbb1\ast\mathbb1=d

    • 莫比乌斯反演：

      莫比乌斯函数有两种定义：
      • 常数函数 1\mathbb1 的逆元称为 μ\mu。
      • 直接定义 μ(n)={1,n=10,∃d,d2∣n(−1)k,∏i=1kpi=n\mu(n)= \begin{aligned}\left\{\begin{matrix} 1,&n=1\\0,&\exist d,d^2\mid n\\(-1)^k,&\prod_{i=1}^kp_i=n \end{matrix}\right.\end{aligned}
      一些常见的卷积：
      • μ∗1=ε\mu\ast1=\varepsilon
      • μ∗id=φ\mu\ast\text{id}=\varphi
      • μ∗d=1\mu\ast d=\mathbb1
      一个变形（也是莫比乌斯反演的另一种理解方式）：
      • f(n)=∑d∣ng(d)⇔g(n)=∑d∣nμ(nd)g(d)f(n)=\sum_{d\mid n}g(d)\Leftrightarrow g(n)=\sum_{d\mid n}\mu(\frac nd)g(d)
        证：f=g∗1⇔g=f∗μf=g\ast \mathbb1\Leftrightarrow g=f\ast\mu。
      通过莫比乌斯反演，我们可以优化一些求和。
      例 1：(重点是交换和式的过程（第 3 步到第 4 步）)
      ∑i=1n∑j=1m[gcd⁡(i,j)=k]=∑i=1n∑j=1m[k∣i][k∣j][gcd⁡(ik,jk)=1]=∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd⁡(i,j)=1](k在1∼n中的倍数有⌊nk⌋个)=∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣i,d∣jμ(d)(ε=μ∗1)=∑d=1min⁡(⌊nk⌋,⌊mk⌋)μ(d)∑i=1⌊nk⌋[d∣i]∑j=1⌊mk⌋[d∣j](只有可以整除i,j的d才能计入答案)(交换求和，是数论的重要trick)=∑d=1min⁡(⌊nk⌋,⌊mk⌋)μ(d)⌊nkd⌋⌊mkd⌋(显然这样的i,j有⌊nkd⌋,⌊mkd⌋个，换句话说就是求d的倍数)\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] &=\sum_{i=1}^n\sum_{j=1}^m[k\mid i][k\mid j][\gcd(\frac ik,\frac jk)=1]\\ &=\sum_{i=1}^{\lfloor \frac nk\rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor}[\gcd(i,j)=1]&(k在1\sim n中的倍数有\lfloor \frac nk\rfloor个)\\ &=\sum_{i=1}^{\lfloor \frac nk\rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor}\sum_{d\mid i,d\mid j}\mu(d)&(\varepsilon=\mu\ast\mathbb1)\\ &=\sum_{d=1}^{\min(\lfloor \frac nk\rfloor,\lfloor \frac mk\rfloor)}\mu(d)\sum_{i=1}^{\lfloor \frac nk\rfloor}[d\mid i]\sum_{j=1}^{\lfloor \frac mk\rfloor}[d\mid j]&(只有可以整除i,j的d才能计入答案)(交换求和，是数论的重要trick)\\ &=\sum_{d=1}^{\min(\lfloor \frac nk\rfloor,\lfloor \frac mk\rfloor)}\mu(d)\lfloor \frac n{kd}\rfloor\lfloor \frac m{kd}\rfloor&(显然这样的i,j有\lfloor \frac n{kd}\rfloor,\lfloor \frac m{kd}\rfloor个，换句话说就是求d的倍数)\\ \end{aligned}
      d(n)d(n) 的一个性质：
      d(i×j)=∑x∣i∑y∣j[gcd⁡(x,y)=1]d(i\times j)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]
      实质是枚举 i,ji,j 的因子，gcd⁡(x,y)=1\gcd (x,y)=1 是为了防止 x,yx,y 和另一对 xgcd⁡(x,y),ygcd⁡(x,y)\frac x{\gcd(x,y)},\frac y{\gcd(x,y)} 重复。

      杜教筛：

      可以在 O(n34)\mathcal O(n^{\frac34}) 的时间内求出积性函数前缀和。
      要求积性函数 ff 的前缀和
      我们定义 S(n)=∑i=1nf(i)S(n)=\sum_{i=1}^nf(i)，再选取一个合适的积性函数 g(n)g(n)。
      我们考虑 (f∗g)=h(f\ast g)=h 的前缀和：
      ∑i=1nh(i)=∑i=1n∑d∣ig(d)f(id)=∑d=1ng(d)∑i=1n[d∣i]f(id)=∑d=1ng(d)∑i=1⌊nd⌋f(i)=∑d=1ng(d)S(⌊nd⌋)\begin{aligned} \sum_{i=1}^nh(i)&=\sum_{i=1}^n\sum_{d\mid i}g(d)f(\frac id)\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^n[d\mid i]f(\frac id)\\ &=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}f(i)\\ &=\sum_{d=1}^ng(d)S(\lfloor\frac nd\rfloor)\\ \end{aligned}
      则有：
      g(1)S(n)=∑d=1ng(d)S(⌊nd⌋)−∑d=2ng(d)S(⌊nd⌋)=∑i=1nh(i)−∑d=2ng(d)S(⌊nd⌋)\begin{aligned} g(1)S(n)&=\sum_{d=1}^ng(d)S(\lfloor\frac nd\rfloor)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)\\ &=\sum_{i=1}^nh(i)-\sum_{d=2}^ng(d)S(\lfloor\frac nd\rfloor)\\ \end{aligned}
      因此我们只需选取一个合适的、可以容易预处理 h,gh,g 前缀和的 gg 即可。
      另外如果先筛出前 n23n^{\frac 23} 个数，复杂度可以优化到 O(n23)\mathcal O(n^{\frac23})。
      杜教筛需配合数论分块、记忆化搜索使用。
      例题 1（P4213 【模板】杜教筛）：
      求
      ∑i=1nφ(i)∑i=1nμ(i)\sum_{i=1}^n\varphi(i)\\ \sum_{i=1}^n\mu(i)
      我们直接用 1\mathbb1 卷，φ\varphi 卷出来是 id\text{id}，μ\mu 卷出来是 ε\varepsilon，于是代码就出来了。
      CPP
      #include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1700000 + 10;

int read(){
int x;
scanf("%lld",&x);
return x;
}

int phi[N],mu[N];
bitset<N>vis;
int p[N],tot;

void init(){
phi[1]=1;
mu[1]=1;
for(int i=2;i<=N-10;i++){
	if(!vis[i]) p[++tot]=i,phi[i]=i-1,mu[i]=-1;
	for(int j=1;j<=tot&&i*p[j]<=N-10;j++){
		vis[i*p[j]]=true;
		if(i%p[j]==0){
			phi[i*p[j]]=p[j]*phi[i];
			mu[i*p[j]]=0;
			break;
		}else{
			phi[i*p[j]]=(p[j]-1)*phi[i];
			mu[i*p[j]]=-mu[i];
		}
	}
}
for(int i=2;i<=N-10;i++) {
	phi[i]=phi[i]+phi[i-1];
	mu[i]=mu[i]+mu[i-1];
}
}
unordered_map<int,int>ans_phi,ans_mu;
int getphi(int n){
if(n<=N-10) return phi[n];
if(ans_phi[n]) return ans_phi[n];
int res=n*(n+1)/2;
for(int l=2,r;l<=n;l=r+1) {
	r=n/(n/l);
	res-=(r-l+1)*getphi(n/l);
}
return ans_phi[n]=res;
}

int getmu(int n){
if(n<=N-10) return mu[n];
if(ans_mu[n]) return ans_mu[n];
int res=1;
for(int l=2,r;l<=n;l=r+1) {
	r=n/(n/l);
	res-=(r-l+1)*getmu(n/l);
}
return ans_mu[n]=res;
}

signed main(){
init();
int t=read();
while(t--){
	int n=read();
	printf("%lld %lld\n",getphi(n),getmu(n));
}
return 0;
}
      这道题的一些细节：
      • 预处理筛出前 O(n23)O(n^{\frac 23}) 的数。
      • 开 long long，不然只有 10pts\texttt{10pts}。
      • 预处理用数组，记忆化搜索用 unordered_map。
      • 不要忘记数论分块，不然只有 30pts\texttt{30pts}。
      • 减号不要写成加号。
      • 要给 φ(1),μ(1)\varphi(1),\mu(1) 赋初值 11

      Lucas 定理：

      若 pp 为质数，则有结论
      (nm)≡(⌊np⌋⌊mp⌋)(n mod pm mod p)(modp)\binom nm\equiv\binom{\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}\binom{n\text{ mod }p}{m\text{ mod }p}\pmod p
      P2480 [SDOI2010] 古代猪文 - 洛谷
      求
      g∑d∣n(nd) mod 999911659g^{\sum \limits_{d\mid n}\binom{n}{d}}\text{ mod }999911659
      用欧拉定理，原式化为
      g∑d∣n(nd) mod 999911658 mod 999911659g^{\sum \limits_{d\mid n}\binom{n}{d}\text{ mod }999911658}\text{ mod }999911659
      有
      999911658=2×3×4679×35617999911658=2\times3\times4679\times35617
      对每个质数求解组合数，然后用 CRT\texttt{CRT} 合并，用快速幂求答案。
      C
      #include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MOD=999911659;
int mod[5]={0,2,3,4679,35617},a[5];
int n,g;
int qp(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int inv(int a,int p){
    return qp(a,p-2,p);
}
int jc[36000],jc_inv[36000];
void pre(int p){
    jc[0]=1;
    for(int i=1;i<p;i++) jc[i]=jc[i-1]*i%p;
    jc_inv[p-1]=inv(jc[p-1],p);
    for(int i=p-2;i>=0;i--) jc_inv[i]=jc_inv[i+1]*(i+1)%p;
}
int C(int n,int m,int p){
    if(m>n) return 0;
    return jc[n]*jc_inv[m]%p*jc_inv[n-m]%p;
}
int lucas(int n,int m,int p){
    if(m==0) return 1;
    return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
void exgcd(int a,int b,int&x,int&y){
    if(!b) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
int crt(){
    int M=MOD-1,ans=0;
    for(int i=1;i<=4;i++){
        int m=M/mod[i];
        int x,y;
        exgcd(m,mod[i],x,y);
        x=(x%mod[i]+mod[i])%mod[i];
        ans=(ans+a[i]*m%M*x%M)%M;
    }
    return ans;
}
signed main(){
    cin>>n>>g;
    if(g==MOD){
        cout<<0;
        return 0;
    }
    for(int k=1;k<=4;k++){
        int p=mod[k];
        pre(p);
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                a[k]=(a[k]+lucas(n,i,p))%p;
                if(i*i!=n) a[k]=(a[k]+lucas(n,n/i,p))%p;
            }
        }
    }
    int p=crt();
    cout<<qp(g,p,MOD);
    return 0;
}

图论部分

树论

树剖

利用线段树在树上进行加值求值求 LCA 等操作，是树上问题的常用帮手
C
struct node{
    int l,r;
    long long z;
    long long lz_add;
}t[800010];

void built(int l,int r,int id){
    t[id].l=l;
    t[id].r=r;
    t[id].lz_add=0;
    if(l==r){
        t[id].z=wt[l]%mod;
        return;
    }
    int mid=(l+r)/2;
    built(l,mid,id*2);
    built(mid+1,r,id*2+1);
    t[id].z=(t[id*2].z+t[id*2+1].z)%mod;
}

void pushdown(int id){
    if(t[id].lz_add!=0){
        t[id*2].lz_add=(t[id*2].lz_add+t[id].lz_add)%mod;
        t[id*2+1].lz_add=(t[id*2+1].lz_add+t[id].lz_add)%mod;
        t[id*2].z=(t[id*2].z+t[id].lz_add*(t[id*2].r-t[id*2].l+1))%mod;
        t[id*2+1].z=(t[id*2+1].z+t[id].lz_add*(t[id*2+1].r-t[id*2+1].l+1))%mod;
        t[id].lz_add=0;
    }
}

void add_range(int x,int y,int k,int id){
    int L=t[id].l,R=t[id].r;
    if(x<=L&&y>=R){
        t[id].lz_add=(t[id].lz_add+k)%mod;
        t[id].z=(t[id].z+k*(R-L+1))%mod;
        return;
    }
    pushdown(id);
    int mid=(L+R)/2;
    if(x<=mid)add_range(x,y,k,id*2);
    if(y>mid)add_range(x,y,k,id*2+1);
    t[id].z=(t[id*2].z+t[id*2+1].z)%mod;
}

long long fd(int x,int y,int id){
    int L=t[id].l,R=t[id].r;
    if(x<=L&&y>=R)return t[id].z;
    pushdown(id);
    int mid=(L+R)/2;
    long long ans=0;
    if(x<=mid)ans=(ans+fd(x,y,id*2))%mod;
    if(y>mid)ans=(ans+fd(x,y,id*2+1))%mod;
    return ans;
}

inline void dfs1(int x,int f,int deep){
    dep[x]=deep;
    fa[x]=f;
    siz[x]=1;
    int maxson=-1;
    for(int i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        siz[x]+=siz[y];
        if(siz[y]>maxson)son[x]=y,maxson=siz[y];
    }
}

inline void dfs2(int x,int topf){
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}

inline int qRange(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=(ans+fd(id[top[x]],id[x],1))%mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=(ans+fd(id[x],id[y],1))%mod;
    return ans;
}

inline void updRange(int x,int y,int k){
    k%=mod;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        add_range(id[top[x]],id[x],k,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    add_range(id[x],id[y],k,1);
}

inline int qSon(int x){
    return fd(id[x],id[x]+siz[x]-1,1);
}

inline void updSon(int x,int k){
    add_range(id[x],id[x]+siz[x]-1,k,1);
}

圆方树：

常用于解决仙人掌类问题，即无自环无重边无向连通任意一条边最多属于一个简单环的图，构造方法为在每个点双构建一个方点，方点与点双内的点连边，其余边舍弃，显然这样的图也是没环的，利用方点存点双信息，圆点存自己信息
仙人掌
C
void tarjan(int u,int fa){
	bool ca=false;
	dfn[u]=low[u]=++tim;st.push(u);
	for(int i=h[u];i;i=edge[i].ne){
		int v=edge[i].e;
		if(v==fa) continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]<dfn[u]){
				if(ca){isc=false;return ; }
				ca=true; 
			}
		}
		else{
			low[u]=min(low[u],dfn[v]);
			if(dfn[v]<dfn[u]){
				if(ca){isc=false;return ; }
				ca=true; 
			}
		}
	}
	if(low[u]==dfn[u]){
		scc_cnt++;int y;
		do{
			y=st.top();st.pop();
			id[y]=scc_cnt;
		}while(y!=u);
	}
}

欧拉路径：

欧拉回路 (路径) 是一条遍历所有边恰好一次的回路 (路径)，点可以重复经过。
有向图存在欧拉回路的充要条件是每个点入度等于出度且图连通。
无向图存在欧拉回路的充要条件是每个点度数为偶数且图连通。
求解可用 dfs
CPP
void dfs(int u){
	for(int i=h[u];i;i=edge[i].ne){
		if(flag[i]) continue;
		flag[i]=flag[i^1]=true;
		int v=edge[i].e;
		dfs(v);
		if(ha[u]<ha[v]) ans[i/2]=0;
		else ans[i/2]=1;
	}
}
常言道如果一道题有点莫名其妙，那它很有可能是用欧拉路径来写
Point and Segment
题意：给定 n 条线段 [li,ri][l_i,r_i], 然后给这些线段红蓝染色，求最后直线上上任意一个点被蓝色及红色线段覆盖次数之差的 ** 绝对值不大于 1 **。
由于是计算绝对值之差，把蓝色看成 1，红色看作 - 1，原题就被转换为了
给定 n 个区间 [li,ri][l_i,r_i]，你可以选择区间并把区间的所有元素 + 1 或 - 1，使得绝对值不大于 1
由于是区间操作，考虑使用差分解决，[li,ri][l_i,r_i] 的 + 1 操作显然就是在 lil_i 处 + 1，ri+1r_i+1 处 - 1，反之同理，这样一个可正可反的，只有 + 1-1 的操作不由地想到了无向边，入的即为 +，出的即为 -，偶数度的点都可以变为 0，跑一遍欧拉回路看边的方向即可知道一种解，奇数度的点显然无法变为 0，且妨碍到了欧拉回路，然而奇数度的点的个数一定是偶数个的，所以考虑把他们两两相连，为了满足题意，把这些点单独拎出来后相邻的两个点差分必须是 - 1，+1，故虚拟边连向相邻的两个点，如果这条边由 A->B，则 B 多加了 1，即为 - 1，A 少加了 1，即为 + 1, 满足题意
由此可见，欧拉回路的题难的不在算法而在建模，转换

二分图：

二分图判定：

使用 dfs01 染色即可，当染色出现矛盾时则说明这不是个二分图
也可以使用 tarjan 判断奇环，若存在奇环则不是二分图

二分图最大匹配：

虽然可以使用网络流算法解决，但没通网不会网络流或者觉得太麻烦也可以使用野蛮人匈牙利算法解决，具体地，可以尝试暴力尝试匹配
CPP
bool match(int x){
	for(int i=n+1;i<=n+m;i++){
		if(t[x][i]&&!vis[i]){
			vis[i]=true;
			if(!p[i]||match(p[i])){p[i]=x;return true;} 
		}
	}
	return false;
}
int hun(){
	int ans=0;
	for(int i=1;i<=n;i++){
		memset(vis,false,sizeof(vis));
		if(match(i)) ans++;
	}
	return ans;
}

网络流：

前言：网络流算法学习不难，难的是建模
下文中若未作特殊声明，S 为源点，T 为汇点

最大流：

** 主要解决问题：** 常用于解决二分图最大问题，具体地，S--> 左端 --> 右端 -->T 连边，左右点之间的连边代表可以匹配，流量为一，最大流即为最大匹配，除了二分图匹配问题，其还能解绝最大流量类问题，需依据不同题意建模

最小割：

引理：将图建成网络，代价 c 设置成对应的容量上限，跑该网络的最大流就是原图的最小割。
反证法：若并非最小割那么一定存在一条路径连通 S 和 T, 就一定存在一条增广路使流量变大，不符合最大流定义
** 主要解决问题：** 最小割主要用于解决二分图最大权独立集问题，集合划分模型，最大权闭合子图问题；
在方格图中，使用对偶图（以面为点，边顺时针旋转 90°）最短路也是一种求最小割的方法，且复杂度优秀

费用流：

即最小费用最大流，使用 dinic 算法，将 bfs 改为 spfa 即可
** 主要解决问题：** 分配收益问题
看似问题少，实则细分下来也有不少小点

技巧部分：

1. 建图技巧
多源多汇：建立超级汇点超级源点
无限之环
点内流量 / 费用限制：拆点为入点出点，限制在连边中体现
[晨跑]([P2153 SDOI2009] 晨跑 - 洛谷 )
利用题目性质优化建图：边数过多时，考虑利用性质优化建图
[卡片]([P2065 TJOI2011] 卡片 - 洛谷 )
当题目有时间限制时，考虑依时间分层 / 分类建图
[家园 / 星际转移问题]([P2754 CTSC1999] 家园 / 星际转移问题 - 洛谷 )
2. 模型
1. 求二分图最大权独立集
同样的 S--> 左端 --> 右端 -->T 连边，中间连 INF, 两边连权值
在网格图中，可以黑白染色来区分连接源点汇点
引理：二分图最大权独立集 = 权值 - 最小割
由此可求出二分图最大权独立集
方格取数问题
2. 集合划分模型：
n 个物品，要划分到 AB 两个集合中，分入某个集合有代价，某些物品被划分到不同区间还有代价，分到相同集合也有代价，求最小代价
对于单独的代价，向集合建一条流量为代价的边
对于不同区间的代价，两点间连一条流量为代价的边
对于相同区间的代价，建立新点向包含点建立流量为 INF 的边，新点向集合连一条流量为代价的边
文理分科
3. 最大权闭合子图
每个点有可负点权，求满足 ∀u∈A   (u,v)∈E,v∈A\forall u \in A\ \ \ (u,v)\in E,v \in A 的最大权子图
由于对于非负权点，需要选择他前面的负权点才可选到，选择负权相当于舍弃权值，不选非负权也是舍弃权值
它能到达的所有点权为负的点连边，再从 s 向点权非负的点分别连边，点权为负的点向 t 连边，那么考虑一种选择对应了什么：
对于一个点权非负的点，要么干脆不选它，要是选了就得舍弃它能到达的所有点权为负的点的点权；
如果不选这个点，就理解成割掉 s 到它的边，而舍弃一个右边的点就理解成割掉它到 t 的边，由此，一种选择对一种割；
将 s 到点权非负的点的边的代价设为其权值，点权为负的点到 t 的边的代价设为其权值的绝对值，其余边代价为 INF，
用点权非负的所有点的权值和减去 s 到 t 的最小割即为答案。
植物大战僵尸
4. 对偶图最短路：
即建立对偶图跑最短路，以面为点，边顺时针旋转 90°，权值不变，建立对偶图，利用多源多汇的技巧建图，跑最短路即可
海拔
5. 最小割树：
当有多组询问两点间最小割且不带修时大概率就是最小割树了
引理：两点之间只有 n 种本质不同的最小割。因此一定存在一棵树，满足树上两点的最小
割等于原图上两点的最小割
具体地，为了求出这样的一颗树采用分治算法，不断以两点 S,T 为源汇跑最小割把集合分开，S 与 T 间建立起最小割大小的边
最小割树
C
void built(int ll,int rr){
	if(ll>=rr) return ;
	s=v[ll];t=v[ll+1];
	memcpy(edge,EDGE,sizeof(EDGE));
	ans=dinic();
	vec[s].push_back(t);vec[t].push_back(s);
	w[s].push_back(ans);w[t].push_back(ans);
	int ltop=ll,rtop=rr;
	for(int i=ll;i<=rr;i++) if(dis[v[i]]!=INF) tmp[ltop++]=v[i];else tmp[rtop--]=v[i];
	for(int i=ll;i<=rr;i++) v[i]=tmp[i];
	built(ll,ltop-1);
	built(rtop+1,rr);
}
int Get(){
	memset(dis,0,sizeof(dis));
	queue<int> q;q.push(s);dis[s]=INF;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<vec[u].size();i++){
			int v=vec[u][i];
			if(!dis[v]){
				dis[v]=min(dis[u],w[u][i]);
				if(v==t) return dis[v];
				q.push(v);
			}
		}
	}
	return dis[t];
}
6. 分配问题：
有 n 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 ci,jc_{i,j}。试设计一个将 n 件工作分配给 n 个人做的分配方案，使产生的总效益最小或最大。
分配问题

板子部分

dinic

C
bool bfs(){
	for(int i=1;i<=n;i++) dis[i]=INF;
	queue<int> q;
	q.push(s);
	dis[s]=0;
	now[s]=h[s];
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=edge[i].ne){
			int v=edge[i].e;
			if(edge[i].w>0&&dis[v]==INF){
				q.push(v);
				now[v]=h[v];
				dis[v]=dis[u]+1;
				if(v==t) return 1;
			}
		}
	}
	return 0;
}
int dfs(int x,long long sum){
	if(x==t) return sum;
	long long k,tmp=0;
	for(int i=now[x];i&&sum;i=edge[i].ne){
		now[x]=i;
		int v=edge[i].e;
		if(edge[i].w>0&&dis[v]==dis[x]+1){
			k=dfs(v,min(sum,edge[i].w));
			if(k==0) dis[v]=INF;
			edge[i].w-=k;
			edge[i^1].w+=k;
			tmp+=k;sum-=k;
		}
	}
	return tmp;
}
void dinic(){
    while(bfs()){
    ans+=dfs(s,INF)
    }
}

HLPP

C
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,s,t;
struct node{
	int e,ne,val;
}edge[500000];
int h[100000],tt=1;
void add(int u,int v,int val){
	edge[++tt].e=v,edge[tt].ne=h[u],edge[tt].val=val,h[u]=tt;
	edge[++tt].e=u,edge[tt].ne=h[v],edge[tt].val=0,h[v]=tt;
}
int hi[100000],gap[100000],E[100000];
bool flag[100000];
void bfs(){
	memset(hi,0x3f,sizeof(hi));
	queue<int> q;q.push(t);
	hi[t]=0;++gap[0];
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=edge[i].ne){
			int v=edge[i].e,val=edge[i].val;
			if(val==0&&hi[v]==0x3f3f3f3f3f3f3f3f){
				hi[v]=hi[u]+1;
				++gap[hi[v]];
				q.push(v);
			}
		}
	}
}
struct cmp{
	inline bool operator()(const int x,const int y){
		return hi[x]<hi[y];
	}
};
priority_queue<int,vector<int>,cmp> pq;
void id(int x){
	--gap[h[x]];
	if(!gap[h[x]]){
		for(int i=1;i<=n;i++){
			if(hi[i]>hi[x]&&i!=s&&i!=t){
				--gap[hi[i]];
				hi[i]=n+1;
			}
		}
	}
	hi[x]=5000;
	for(int i=h[x];i;i=edge[i].ne){
		int v=edge[i].e,val=edge[i].val;
		if(val>0&&hi[v]+1<hi[x]){
			hi[x]=hi[v]+1;
		}
	}
	++gap[hi[x]];
}
void HLPP(){
	bfs();
	hi[s]=n;
	for(int i=h[s];i;i=edge[i].ne){
		int v=edge[i].e,val=edge[i].val;
		if(val>0){
			E[v]+=val;
			edge[i].val-=val,edge[i^1].val+=val;
		}
		if(v!=t&&v!=s&&!flag[v]){
			pq.push(v);flag[v]=true;
		}
	}
	while(!pq.empty()){
		int u=pq.top();pq.pop();
		flag[u]=false;
		for(int i=h[u];i;i=edge[i].ne){
			int v=edge[i].e,val=edge[i].val;
			if(val>0&&hi[u]==hi[v]+1){
				int f=min(val,E[u]);
				E[u]-=f,E[v]+=f;edge[i].val-=f,edge[i^1].val+=f;
				if(!flag[v]&&v!=s&&v!=t){
					pq.push(v);flag[v]=true;
				}
			}
			if(!E[u]) break;
		}
		if(E[u]!=0){
			id(u);
			pq.push(u);flag[u]=1;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1,x,y,z;i<=m;i++){
    	cin>>x>>y>>z;
    	add(x,y,z);
	}
	HLPP();
	cout<<E[t];
	return 0;
}

数据结构部分

**0 / 1 trie:** 用于解决位运算问题（尤其异或）[最长异或路径](P4551 最长异或路径 - 洛谷 )
线段树合并：序列合并类的题 雨天的尾巴
线段树合并的方式多种多样，但本质上是合并相同节点，复制未有节点
李超线段树：维护凸包用，函数必须满足只有一个交点，否则李超线段树正确性无法被保证
C
struct line{
	double k,b;
}p[400001];
int s[414514];
int cmp(double x,double y){
	if(x-y>1e-9) return 1;
	if(y-x>1e-9) return -1;
	return 0;
}
inline double js(int id,int x){
	return p[id].k*x+p[id].b;
}
inline void add(int x0,int yy0,int x1,int yy1){
	if(x0==x1) p[++cnt].k=0,p[cnt].b=max(yy0,yy1);
	else p[++cnt].k=1.0*(yy1-yy0)/(x1-x0),p[cnt].b=yy0-p[cnt].k*x0;
}
void upd(int root,int L,int R,int u) {
    int &v=s[root],mid=(L+R)>>1;
    if(v==0){v=u;return;}
    double lu=js(u,L),ru=js(u,R);
    double lv=js(v,L),rv=js(v,R);
    if(cmp(lu,lv)>0&&cmp(ru,rv)>0) {v=u;return;}
    if(cmp(lu,lv)<=0 &&cmp(ru,rv)<=0) return;
    int bmid=cmp(js(u,mid),js(v,mid));
    if(bmid==1||(bmid==0&&u<v)) swap(u,v);
    if(cmp(js(u,L),js(v,L))>0||(cmp(js(u,L),js(v,L))==0&&u<v)) upd(root<<1, L, mid, u);
    if(cmp(js(u,R),js(v,R))>0||(cmp(js(u,R),js(v,R))==0&&u<v)) upd(root<<1|1, mid+1, R, u);
}
void update(int root,int L,int R,int l,int r,int u){
	if(l<=L&&R<=r){
		upd(root,L,R,u);
		return ;
	}
	int mid=(L+R)>>1;
	if(l<=mid) update(root<<1,L,mid,l,r,u);
	if(mid<r) update(root<<1|1,mid+1,R,l,r,u);
}
pair<double,int> pmax(pair<double,int> x,pair<double,int> y){
	if(cmp(x.first,y.first)==-1) return y;
	if(cmp(x.first,y.first)==1) return x;
	else return x.second<y.second?x:y;
}
pair<double,int> query(int root,int L,int R,int x){
	if(R<x||x<L) return {-1e18,0};
	int mid=(L+R)>>1;
	double ans=js(s[root],x);
	if(L==R) return {ans,s[root]};
	return pmax({ans,s[root]},pmax(query(root<<1,L,mid,x),query(root<<1|1,mid+1,R,x)));
}

根号算法部分

分块：

暴力这 n\sqrt{n} 块

序列分块：

将一个序列分成 B 块，修改的同时维护块内性质，查询时若在块内则暴力，否则整块利用先前的维护求值，散块暴力求解，具体块的大小需根据题目修改，但大部分都是 n\sqrt{n} 的大小
例题：蒲公英
题意概括：给出长度为 n 的序列，询问 [l,r][l,r] 的众数
以此题为例，细讲如何推导最佳块大小，维护前缀和，然而数的种类太多，空间无法承受，于是分块储存前缀和，这里没有修改操作，维护，储存前缀和，整块内众数，数字出现位置即可，区间众数只会出现在整块众数与散块中的数中，预处理是 (n/B)2(n/B)^2 的，询问是 q×(2×B×log⁡(此数字出现个数))q \times(2\times B \times \log (此数字出现个数)) 的，由于值域大个数少 log 几乎可以当作常数看待，总复杂度是 n2B2+2qB\frac{n^2}{B^2} +2qB 的发现 q 和 n 差不多大小，把 q 当作 n 看待，利用基础不等式可以推得 B=n3B=\sqrt[3]{n} 是优秀的，这里也可以取 B=n23B=\sqrt[3]{\frac{n}{2}} 但空间上有点紧；

莫队：

普通莫队：
有许多询问 [l,r][l,r], 且对于有交集的地方的处理是相同的，则可以使用莫队来处理，莫队的基础是双指针法，本质上相当于是为了构造一条经过所有点（l,r）的路径，每次只能移动一个单位，使得路径长度尽可能短。
对 l 进行分块 按照块顺序为第一关键字，r 为第二关键字进行排序（可以进行奇偶优化），移动距离约为 （qB+n2B）（qB+\frac{n^2}{B}） 同样基本不等式取 （nq）（\frac{n}{\sqrt{q}}） 即可
附奇偶优化 cmp
CPP
bool cmp(node a,node b){
    int block_a=a.l/siz;
    int block_b=b.l/siz;
    if(block_a!=block_b)return block_a<block_b;
    return (block_a&1)?a.r<b.r:a.r>b.r;
}
[小 Z 的袜子]([P1494 国家集训队] 小 Z 的袜子 - 洛谷 )
莫队二次离线：
第一次离线莫队，第二次离线做扫描线，和普通莫队的区别是贡献部分用扫描线的方法计算，此算法适用于
**「区间计算有多少满足条件点对」** 问题，具体的
[Yuno loves sqrt technology II]([P5047 Ynoi2019 模拟赛] Yuno loves sqrt technology II - 洛谷 )
区间查询逆序对数

动态规划部分

数据结构优化 dp

线段树优化 dp: 士兵
李超线段树优化 dp:[Building Bridges]([P4655 CEOI 2017] Building Bridges - 洛谷 )
这两类的区别主要体现在 dp 式子上，若是 1D 的式子则大概率线段树，2D 的式子则大概率李超线段树

状压 dp

[寿司晚宴]([P2150 NOI2015] 寿司晚宴 - 洛谷 )
把 dp 的选与不选压缩为 01，构造二进制数进行状态压缩

DDP:

前置：

广义矩阵乘法：
对于 ⊕\oplus 和 ⊗\otimes 这两种运算，若有
  • ⊗\otimes 有交换律：a⊗b=b⊗aa \otimes b = b \otimes a
  • ⊗\otimes 有结合律：(a⊗b)⊗c=a⊗(b⊗c)(a \otimes b) \otimes c= a \otimes (b \otimes c)
  • ⊗\otimes 对 ⊕\oplus 有分配律：a⊗(b⊕c)=(a⊗b⊕a⊗c)a \otimes(b \oplus c)=(a \otimes b \oplus a \otimes c);
则有广义矩阵乘法
常见的有 ⊕\oplus 是 +，⊗\otimes 是 ×\times
C
jz operator *(const jz &x,const jz &y){
	jz z;
	for(int k=1;k<=sz;k++){
		for(int i=1;i<=sz;i++){
			for(int j=1;j<=sz;j++){
				z.a[i][j]=(z.a[i][j]+x.a[i][k]%mod*y.a[k][j]%mod)%mod;
			}
		}
	}
	return z;
}
⊕\oplus 是 min、max，⊗\otimes 是 +
C
jz operator *(const jz &x,const jz &y){
	jz z;
	for(int i=1;i<=sz;i++)
	    for(int j=1;j<=sz;j++)
	        z.a[i][j]=INF;
	for(int k=1;k<=sz;k++)
	    for(int i=1;i<=sz;i++)
	        for(int j=1;j<=sz;j++)
	            z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]);
	return z;
}

解题：

此类题需要将转移写成矩阵形式
例如 New Year and Old Subsequence
有
{fi,0={fi−1,0+1(si=2)fi−1,0(si≠2)fi,1=min⁡({fi−1,1+1(si=0)fi−1,1(si≠0),{fi−1,0(si=2)inf⁡(si≠2))fi,2=min⁡({fi−1,2+1(si=1)fi−1,2(si≠1),{fi−1,1(si=0)inf⁡(si≠0))fi,3=min⁡({fi−1,3+1(si=7 or si=6)fi−1,3(si≠7 and si≠6),{fi−1,2(si=1)inf⁡(si≠1))fi,4=min⁡({fi−1,4+1(si=6)fi−1,4(si≠6),{fi−1,3(si=7)inf⁡(si≠7))\left\{\begin{array}{l} f_{i, 0}=\left\{\begin{array}{l} f_{i-1,0}+1\left(s_{i}=2\right) \\ f_{i-1,0}\left(s_{i} \neq 2\right) \end{array}\right. \\ f_{i, 1}=\min \left(\left\{\begin{array}{l} f_{i-1,1}+1\left(s_{i}=0\right) \\ f_{i-1,1}\left(s_{i} \neq 0\right) \end{array},\left\{\begin{array}{l} f_{i-1,0}\left(s_{i}=2\right) \\ \inf \left(s_{i} \neq 2\right) \end{array}\right)\right.\right. \\ f_{i, 2}=\min \left(\left\{\begin{array}{l} f_{i-1,2}+1\left(s_{i}=1\right) \\ f_{i-1,2}\left(s_{i} \neq 1\right) \end{array},\left\{\begin{array}{l} f_{i-1,1}\left(s_{i}=0\right) \\ \inf \left(s_{i} \neq 0\right) \end{array}\right)\right.\right. \\ f_{i, 3}=\min \left(\left\{\begin{array}{l} f_{i-1,3}+1\left(s_{i}=7 \text { or } s_{i}=6\right) \\ f_{i-1,3}\left(s_{i} \neq 7 \text { and } s_{i} \neq 6\right) \end{array},\left\{\begin{array}{l} f_{i-1,2}\left(s_{i}=1\right) \\ \inf \left(s_{i} \neq 1\right) \end{array}\right)\right.\right. \\ f_{i, 4}=\min \left(\left\{\begin{array}{l} f_{i-1,4}+1\left(s_{i}=6\right) \\ f_{i-1,4}\left(s_{i} \neq 6\right) \end{array},\left\{\begin{array}{l} f_{i-1,3}\left(s_{i}=7\right) \\ \inf \left(s_{i} \neq 7\right) \end{array}\right)\right.\right. \end{array}\right.
可以转换为
[fi−1,0fi−1,1fi−1,2fi−1,3fi−1,4]×[(si=2)?1:0(si=2)?0:inf⁡inf⁡inf⁡inf⁡inf⁡(si=0)?1:0(si=0)?0:inf⁡inf⁡inf⁡inf⁡inf⁡(si=1)?1:0(si=1)?0:inf⁡inf⁡inf⁡inf⁡inf⁡(si=7 or si=0)?1:0(si=7)?0:inf⁡inf⁡inf⁡inf⁡inf⁡(si=6)?1:0]\left[ f_{i-1,0}\quad f_{i-1,1}\quad f_{i-1,2}\quad f_{i-1,3}\quad f_{i-1,4} \right] \times \left[ \begin{array}{ccccc} (s_i=2)?1:0 & (s_i=2)?0:\inf & \inf & \inf & \inf \\ \inf & (s_i=0)?1:0 & (s_i=0)?0:\inf & \inf & \inf \\ \inf & \inf & (s_i=1)?1:0 & (s_i=1)?0:\inf & \inf \\ \inf & \inf & \inf & (s_i=7\ or\ s_i=0)?1:0 & (s_i=7)?0:\inf \\ \inf & \inf & \inf & \inf & (s_i=6)?1:0 \\ \end{array} \right]
用线段树维护即可
如若想在树上使用该算法可以使用树剖
保卫王国

决策单调性优化 dp:

fi=min⁡1≤j≤i(wj,i)f_i= \min _{1\le j \le i}(w_{j,i})
gig_i 表示令 wi,jw_{i,j} 最小的 j，若 ∀i<j,gi≤gj\forall i<j,g_i \le g_j 则称这个问题有决策单调性
若对于上述的 w(l,r)w(l,r)
∀l1≤l2≤r1≤r2,w(l1,r1)+w(l2,r2)≤w(l1,r2)+w(l2,r1)\forall l_1 \le l_2 \le r_1 \le r_2,w(l_1,r_1)+w(l_2,r_2) \le w(l_1,r_2)+w(l_2,r_1)
即交叉优于包含
则这个式子满足决策单调性，可以用分治或队列 \ 栈优化
队列 \ 栈优化 诗人小 G
C
long double qpow(long double x,int p){
    if(!p) return 1.0;
    long double sum=x,ans=1;
    while(p){
        if(p&1) ans*=sum;
        p>>=1;sum*=sum;
    }
    return ans;
}
long double calc(int i,int j){
    return dp[j]+qpow((long double)abs(sum[i]-sum[j]+i-j-l-1),p);
}
 int find(int j,int i){
    int l=j+1,r=n+1;
    while(l<r){
        int mid=(l+r)>>1;
        if(calc(mid,j)>=calc(mid,i)) r=mid;
        else l=mid+1;
    }
    return l;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>l>>p;
        for(int i=1;i<=n;i++) 
            cin>>s[i],sum[i]=strlen(s[i]+1)+sum[i-1]+1;
        
        q[h=t=1]=0;
        for(int i=1;i<=n;i++){
            while(h<t&&k[h]<=i) h++;
            pre[i]=q[h];
            dp[i]=calc(i,q[h]);
            while(h<t&&k[t-1]>=find(q[t],i)) t--;
            k[t]=find(q[t],i);
            q[++t]=i;
        }
        
        if(dp[n]>1e18) cout<<"Too hard to arrange\n";
        else{
            cout<<(long long)dp[n]<<'\n';
            int stk[100007],top=0;
            for(int i=n;i;i=pre[i]) stk[++top]=i;
            for(int i=top,last=0;i>=1;i--){
                for(int j=last+1;j<stk[i];j++)
                    cout<<s[j]<<' ';
                cout<<s[stk[i]]<<'\n';
                last=stk[i];
            }
        }
        cout<<"--------------------\n";
    }
    return 0;
}
分治优化 灯塔
C
void so(int l,int r,int L,int R){
	if(l>r) return ;
	int mid=l+r>>1,opt=L;
	for(int i=L+1;i<=min(mid,R);i++) if(js(mid,opt)<js(mid,i)) opt=i;
	p[mid]=max(p[mid],js(mid,opt));
	so(l,mid-1,L,opt);
	so(mid+1,r,opt,R); 
}

wqs 二分

当出现 2D 的转移式子时，我们不仅能用李超线段树维护凸壳，wqs 也是一种在解决恰有 k 个物品的最大 \ 最小价值问题时的方法
若恰好 x 个物品的价值 f(x)f(x) 是一个下凸函数，则可以使用，我们为每多选一个物品加一个惩罚，惩罚越大选用物品的个数就越少，惩罚越小就越多，因此我们可以不断调整这个惩罚来逼近 k
忘情
CPP
bool check(int mid){
	memset(f,0x3f,sizeof(f));
	memset(g,0,sizeof(g));
	f[0]=0,opt[1]=0;
	int l=1,r=1;
	for(int i=1;i<=n;i++){
		while (l<r&&(Y(opt[l+1])-Y(opt[l]))/(s[opt[l+1]]-s[opt[l]])<2*s[i]) l++;
		f[i]=f[opt[l]]+(s[i]-s[opt[l]]+1)*(s[i]-s[opt[l]]+1)+mid;
		g[i]=g[opt[l]]+1;
		while (l<r&&(long double)(Y(opt[r-1])-Y(opt[r]))/(s[opt[r-1]]-s[opt[r]])>(long double)(Y(opt[r-1])-Y(i))/(s[opt[r-1]]-s[i])) r--;
		opt[++r]=i;
	}
	return g[n]<=m;
}
signed main(){
    int l=-1e18,r=1e18,ans=0;
    while(l<=r){
    	int mid=(l+r)>>1;
    	if(check(mid)) r=mid-1,ans=mid;
    	else l=mid+1;
	}
	check(ans);
	cout<<f[n]-m*ans; 
	return 0;
}
注意答案不要忘记减去惩罚

插入 dp

插入类 dp 核心在于以某种顺序插入元素，这样可以确保前面元素的限制小于后面的，从而简化了状态转移的复杂性
这类 dp 的状态设计为插入 i 个元素，已形成 j 个连续段
转移通常为
  • 新开一段
  • 合并两段
  • 放在某端边缘
对于左右端点需要特判

字符串算法

Manacher

Manacher 算法是一种用于求解单串回文结构的算法，可以求出以位置 i 为中心的最长回文串的半径长度，这个信息，对于处理回文串问题有非常大帮助。
具体地，将 s 的相邻两个字符之间添一个相同的罕见字符，
考虑用 p[1], · · · , p[i − 1] 递推 p[i]。定义 mr 表示之前的 i + p[i] − 1 的最大值 (即最靠右的回文串)。同时记录这个回文中心为 mid (如果有多个，记录最靠右的)。
考虑当前位置 i：
  • 如果 i ≤ mr，则设置初值为 p[i] = min(p[mid ∗ 2 − i], mr − i + 1)。
  • 否则设置初值为 p[i] = 1。
之后暴力向两侧扩展 p[i]，并更新 mid 和 mr。
C
void build(){
    scanf("%s",c+1),n=strlen(c+1),s[++cnt]='~',s[++cnt]='#';
    for(int i=1;i<=n;i++) s[++cnt]=c[i],s[++cnt]='#';
    s[++cnt]='!';
}
void solve(){
    for(int i=2;i<=cnt-1;i++){
        if(i<=mr) p[i]=min(p[mid*2-i],mr-i+1);
        else p[i]=1;
        while(s[i+p[i]]) ++p[i];
        if(i+p[i]>mr) mr=i+p[i]-1,mid=i;
        ans=max(ans,p[i]);
    }
    cout<<ans-1;
}

分治算法

线段树分治

Bipartite Checking
从这个线段树分治板子题，从头整理一下线段树分治的一些重点。
首先看到本题，如果只有添加边一种操作的话，显然是可以用扩展域并查集维护的，如果不会可以翻到本文最后面有讲。
但是本题有删除边的操作，这就不能只用并查集维护了。
我们考虑一个 O(n2)O(n^2) 的暴力（设 n,mn,m 同阶），对每一个询问，找到有哪些边在这个询问时是存在的，然后直接在空并查集上加边，最后判断是否为二分图。
考虑这个暴力不足的地方：由于操作是对一个时间区间都存在，有一些边在下一个询问中仍然是存在的，但是我们将其全部删掉了。我们的并查集虽然不能支持删除边，但是可以撤销！如果我们知道相对下一个询问，我们需要撤销哪些边，再加上哪些边，是不是可以优化复杂度呢？

线段树分治的思想

我们对时间（询问）建立一颗线段树，树的节点存的信息是【覆盖了这个区间的操作】。
考虑遍历整颗线段树，维护一颗可撤销并查集。当进入一个线段树的子节点时，在并查集上添加覆盖这个区间的边。然后继续递归子节点，直到叶子节点（对应的就是一个询问），统计对应的答案。回溯时，将这个节点加的边在并查集上撤销。
这样，递归到每一个叶子节点时，并查集中的边都是这个询问的完整状态。
分析复杂度，遍历线段树的时间是 O(nlog⁡n)O(n\log n) 的，总共 O(n)O(n) 个操作，每一个操作在线段树上最多覆盖 log⁡n\log n 个节点，可撤销并查集由于不能使用路径压缩，所以按秩合并的复杂度是 O(log⁡n)O(\log n) 的，维护操作的复杂度是 O(nlog⁡2n)O(n\log^2n) 的。
这就是线段树分治。

看到什么应该想到线段树分治？

  • 多个操作，每一个操作的影响范围是一个区间（时间区间，询问区间）。
  • 多个询问，询问（某个时间时，某个操作后的）答案。
比如本题：操作为删除或者添加边，也就是说一条边的影响范围是一个区间。同时在每一次操作后求答案（是否为二分图）。

实现

CPP
struct BCJ
{
    int n;
    int fa[200010];
    int dep[200010];
    void init(int x){
        n=x;
        for(int i=1;i<=2*n;i++){
            fa[i]=i;
            dep[i]=1;
        }
    }
    int find(int x){
        return x==fa[x]?x:find(fa[x]);
    }
    void merge(int x,int y,stack<int>&sta){
        x=find(x),y=find(y);
        if(x==y)return;
        if(dep[x]<dep[y])swap(x,y);
        fa[y]=x;
        dep[x]=max(dep[x],dep[y]+1);
        sta.push(y);
    }
    void roll_back(stack<int>&sta){
        while(!sta.empty()){
            int x=sta.top();
            sta.pop();
            fa[x]=x;
        }
    }
}bcj;
struct EDGE{
    int x,y;
}edge[200010];
vector<int> tr[800010];
int n,m;
bitset<200010>ans;
void update(int now,int l,int r,int ll,int rr,int e){
    if(l>rr||r<ll)return ;
    if(ll<=l&&rr>=r){
        tr[now].push_back(e);
        return ;
    }
    int mid=l+r>>1;
    update(now<<1,l,mid,ll,rr,e);
    update(now<<1|1,mid+1,r,ll,rr,e);
}
void getans(int now,int l,int r){
    stack<int>sta;
    for(auto x:tr[now]){
        if(bcj.find(edge[x].x)==bcj.find(edge[x].y)){
            for(int i=l;i<=r;i++) ans[i]=0;
            bcj.roll_back(sta);
            return ;
        } 
        bcj.merge(edge[x].x,edge[x].y+n,sta);
        bcj.merge(edge[x].x+n,edge[x].y,sta);
    }
    if(l!=r){
        int mid=l+r>>1;
        getans(now<<1,l,mid);
        getans(now<<1|1,mid+1,r);
    }
    bcj.roll_back(sta);
}
map<pair<int,int>,int>mp;
int cnte=0;
signed main(){
    ans.set();
    cin>>n>>m;
    bcj.init(n);
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(mp[{x,y}]){
            int from=mp[{x,y}];
            cnte++;
            edge[cnte].x=x,edge[cnte].y=y;
            update(1,1,m,from,i-1,cnte);
            mp[{x,y}]=0;
        }
        else mp[{x,y}]=i;
    }
    for(auto x:mp){
        if(x.second){
            cnte++;
            edge[cnte].x=x.first.first,edge[cnte].y=x.first.second;
            update(1,1,m,x.second,m,cnte);
        }
    }
    getans(1,1,m);
    for(int i=1;i<=m;i++) cout<<(ans[i]?"YES\n":"NO\n");
}
不太熟练所以线段树分治题单
AFO啦，留给大学的我

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...