[NOI2024] 登山
这是第一个我自己写出来的树形 DP 黑题。
题目链接： [NOI2024] 登山 。
题目描述：
“为什么要攀登？因为山就在那里。”
慕士塔格山上有 nnn 处点位，点从 111 到 nnn 编号，111 号点位为山顶。这 nnn 个点位构成一棵有根树的结构，其中 111 号点位为根，对于 2≤i≤n2\leq i\leq n2≤i≤n，iii 号点位的父亲结点为 pip_ipi 号点位。
记 did_idi 为 iii 号点位到山顶所需经过的边数。形式化地说，d1=0d_1=0d1=0，对于 2≤i≤n2\leq i\leq n2≤i≤n，di=dpi+1d_i=d_{p_i}+1di=dpi+1。
定义一条登山路径为从 2∼n2\sim n2∼n 号点位中的某一个开始，经过若干次移动后到达山顶的方案。
定义一次从 i(2≤i≤n)i(2\leq i\leq n)i(2≤i≤n) 号点位出发的移动为以下两种方式之一：
冲刺：在给定的冲刺范围 [li,ri][l_i,r_i][li,ri] 内，选择一个正整数 kkk 满足 li≤k≤ri ...
NOI 记
加油 NOI 。
P5755 [NOI2000] 单词查找树
【模板】字典树。
题目链接： [NOI2000] 单词查找树 。
题目描述：
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
在满足上述条件下，该单词查找树的节点数最少。
对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）。
这个题有意思的点是，它直接把字典树是啥告诉你了，所以这也是一个简单模拟题。
代码：
12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;const int N=100010;string s;int nxt[N][26];int ...
省选联考记
加油省选。
P7518 [省选联考 2021 A/B 卷] 宝石
这个算是一个比较基础的倍增题目了。
题目链接： [省选联考 2021 A/B 卷] 宝石 。
题目内容:
给一颗树，树上每个点有点权。
每次求序列 P1,P2,...PcP_1,P_2,...P_cP1,P2,...Pc （ ccc 为每次询问给的， PPP 为预先定好的序列）是否是 sss 到 ttt 路径上点权构成的序列的子序列。
n,q≤2×105n,q \le 2\times 10^5n,q≤2×105 。
这个信息并不好维护。但是考虑到 PPP 为定序列，我们可以预处理树上每个点 iii 往上走，跨越 PPP 序列上 2j2^j2j 个点后到达的点。
对于 PPP 序列的正序和逆序都需要倍增存储。
这个东西是可以通过可持久化线段树维护的。
设正序倍增数组为 upi,jup_{i,j}upi,j ，逆序为 dni,jdn_{i,j}dni,j 。
那么首先我们求出 s,ts,ts,t 的 lcalcalca ，设为 lll 。
然后倍增跳跃，每次比较跳到的点和 lll 的深度，从而比 ...
UGreen Cloud-space: A better choice for cloud-space
Have you ever been anxious for a big and free cloud-space?
Have you erer used Baidu Cloud-space or Quark Cloud-space and been angry when your VIP was due?
Let’s use UGreen Cloud-Space!
The common aspects of UGreen Cloud-space
UGreen Cloud-space is a website which can memorize your files which you want to upload.
Like other cloud-spaces, UGreen Cloud-space enable you to upload or download your files whenever you click choice “Upload” or “Downl ...
[NOIP2022] 建造军营
题目： [NOIP2022] 建造军营 。
这是我第一个自己写出来的组合数学和树形 DP 的题目。
题目内容：
给定 nnn 个点 mmm 条边的无向联通简单图，可以在任意多个点（至少一个）建立军营，在任意多条边建立士兵。
求有多少种建造方案数使得任意切断一条没有士兵的边后，所有军营依然联通。
n≤5×105,m≤106n \le 5\times 10^5,m\le 10^6n≤5×105,m≤106 。
时间限制 1.00s1.00s1.00s ，内存限制 512.00MB512.00MB512.00MB ，期望复杂度 O(n+m)O(n+m)O(n+m) 。
首先，看到这个题目，这其中 所有军营依然联通 的限制让我们想到边双缩点后在树上求解，这是因为在边双中任意断边后边双内任意两点仍然联通。
问题就转变为了在一个树上求解。
设一个边双 iii 内有 aia_iai 个点和 bib_ibi 条边。
如果设 fif_ifi 表示以 iii 为根的子树内的答案， ∑bi\sum b_i∑bi 为以 iii 为根的子树内的边数，那么这里我们需要 ...
转置原理
初等矩阵
众所周知，矩阵的初等变换有以下三种：
交换第 iii 行（列）和第 jjj 行（列）。
将第 iii 行（列）乘上 kkk 。
将第 iii 行（列）的 kkk 倍对应加到第 jjj 行（列）上。
同时，我们还知道单位矩阵 III ：
[10⋯001⋯0⋮⋮⋮⋮00⋯1]\begin{bmatrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \vdots \\
0 & 0 & \cdots & 1
\end{bmatrix}⎣⎢⎢⎢⎢⎡10⋮001⋮0⋯⋯⋮⋯00⋮1⎦⎥⎥⎥⎥⎤
对于任意矩阵 AAA ，有 A×I=I×A=AA\times I=I\times A=AA×I=I×A=A 。
若将初等变换作用在 III 上，就可以得到初等矩阵 EEE ：
对于初等行变换，则 E×AE \times AE×A 为对 AAA 进行初等行变换。
对于初等列变 ...
数论
我为什么会写这个？
整除分块
如果你想在 O(n)O(\sqrt{n})O(n) 时间内求解如下式子：
∑i=1nf(i)g(⌊ni)⌋\sum_{i=1}^n f(i)g(\lfloor\frac{n}{i})\rfloor
i=1∑nf(i)g(⌊in)⌋
满足 O(1)O(1)O(1) 求取 fff 函数的前缀和， O(1)O(1)O(1) 求取 ggg 函数单点值。
这时候就需要用到整除分块了。
看引理：
引理 1 ：
⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in⌋ 的不同取值个数为 O(n)O(\sqrt{n})O(n) 个。
引理 2 ：
对于整数 kkk ，对于所有的 iii 满足 ⌊ni⌋=k\lfloor\frac{n}{i}\rfloor=k⌊in⌋=k ， iii 的取值连续。
那么我们可以枚举这 O(n)O(\sqrt{n})O(n) 个取值，从而在 O(n)O(\sqrt{n})O(n) 内求解。
但是我们还有一个问题：假设当前枚举的取值为 ⌊nl⌋\lfloor\frac{n}{l}\rfloor⌊ln ...
组合数学与计数 DP （二）
其实 FFT 也算组合数学。
Lucas 定理
给定 n,m,pn,m,pn,m,p ，保证 ppp 为质数，求 Cn+mm mod pC_{n+m}^m \bmod pCn+mmmodp 。
题目： Lucas 定理 。
Lucas 定理：
若 ppp 为质数，则有：
Cnm mod p=C⌊np⌋⌊mp⌋Cn mod pm mod p mod pC_n^m \bmod p=C_{\lfloor \frac{n}{p}\rfloor}^{\lfloor \frac{m}{p}\rfloor}C_{n \bmod p}^{m \bmod p} \bmod p
Cnmmodp=C⌊pn⌋⌊pm⌋Cnmodpmmodpmodp
证明：
引理 2 ：
对于质数 ppp ，有 (1+x)p≡1+xp(modp)(1+x)^p \equiv 1+x^p \pmod p(1+x)p≡1+xp(modp) 。
令 n=ap+b,m=cp+dn=ap+b,m=cp+dn=ap+b,m=cp+d 。
则有：
(1+x)n≡(1+x)ap(1+x)b ...
组合数学与计数 DP
这东西博大精深……
前置内容
排列组合
nnn 个数的排列：将这些数放在一个序列中，与这些数的顺序有关。 例如， 1,2,31,2,31,2,3 和 3,2,13,2,13,2,1 是不同的排列。
nnn 个数的组合：将这些数放在一个可重集中，与这些数的顺序无关。 例如， {1,2,3}\{1,2,3\}{1,2,3} 和 {1,3,2}\{1,3,2\}{1,3,2} 是同一个组合。
AnmA_n^mAnm ，表示从 nnn 个不同的数中选 mmm 个数进行排列的方案数。
CnmC_n^mCnm ，表示从 nnn 个不同的数中选 mmm 个数进行组合的方案数。
引理 1 ：
Anm=n!(n−m)!A_n^m=\frac{n!}{(n-m)!}
Anm=(n−m)!n!
Cnm=n!m!(n−m)!C_n^m=\frac{n!}{m!(n-m)!}
Cnm=m!(n−m)!n!
证明：
AnmA_n^mAnm 可以看作将 nnn 个不同的数选 mmm 个数放在一个长度为 mmm 的序列上。序列的顺序重要。 所以第一个位置上可以放 nnn ...
快速傅里叶变换 FFT （二）
Chirp-Z Transform
FFT 可以求单位根为公比的等比数列在多项式函数上的点值。
Chirp-Z Transform 是一种可以求任意数为公比的任意长度的等比数列在多项式函数上的点值。
设 nnn 次多项式 P(x)=∑i=0n−1aixiP(x)=\displaystyle\sum_{i=0}^{n-1}a_ix^iP(x)=i=0∑n−1aixi 和整数 c,mc,mc,m ，则 Chirp-Z Transform 可以快速求出 P(1),P(c),P(c2)⋯P(cm−1)P(1),P(c),P(c^2)\cdots P(c^{m-1})P(1),P(c),P(c2)⋯P(cm−1) 。
引理 12 ：
ij=Ci+j2−Ci2−Cj2ij=C_{i+j}^2-C_i^2-C_j^2
ij=Ci+j2−Ci2−Cj2
证明显然。
设 ansi=P(ci)ans_i=P(c^i)ansi=P(ci) ，则有：
ansi=∑j=0n−1ajcijans_i=\sum_{j=0}^{n-1} a_jc^{ij}
ansi ...
