「CF708E」 Student’s Camp
CodeForces 708E
动态规划，dp优化
题意
给你一个 n+2n+2n+2，宽 mmm 的矩形，其中第 111 行和第 n+1n+1n+1 行是坚不可摧的。有 ttt 天，每天对于每行有 ppp 的概率消掉最左块，同样的也有 ppp 的概率消掉最右块。求 ttt 天后所有格子构成一个联通块的概率。
1≤n,m≤1500,0≤t≤1000001\le n,m\le 1500,0\le t\le 100000
1≤n,m≤1500,0≤t≤100000
题解
能消掉的只有 nnn 行 mmm 列，对于一行，在 ttt 天后留下 [l,r][l,r][l,r] 这段的概率为
(tl−1)pl−1(1−p)t−l+1×(tm−r)pm−r(1−p)t−m+r\binom{t}{l-1}p^{l-1} (1-p)^{t-l+1} \times \binom{t}{m-r} p^{m-r}(1-p)^{t-m+r}
(l−1t)pl−1(1−p)t−l+1×(m−rt)pm−r(1−p)t−m+r
记 Gl=(tl−1)pl−1(1−p)t−l+1,Hr=(tm−r)pm−r(1 ...
TC - 12118 ConversionMachine
TopCoder - 12118
单位根反演，指数生成函数。
题意
给你两个仅包含 a,b,c\texttt{a,b,c}a,b,c 字符串 A,BA,BA,B（∣A∣,∣B∣≤11|A|,|B|\le 11∣A∣,∣B∣≤11），以及一个长度为 333 的数组分别表示 a→b,b→c,c→a\texttt{a}\to\texttt{b},\texttt{b}\to\texttt{c},\texttt{c}\to\texttt{a}a→b,b→c,c→a 的代价，和 Maxcost(≤109)Maxcost (\le 10^9)Maxcost(≤109)，问在不超过 MaxcostMaxcostMaxcost 将 AAA 变成 BBB 的方案数。两种方案视为不同的，当存在一个位置，两个方案改变了不同的位置的字符。
题解
每个位置若 Ai≠BiA_i\ne B_iAi=Bi ，先要花费一定步数使其变到 BBB 。然后每个位置再可以变三的倍数次。
题意转化为每个位置操作次数为 ci=3k+ai(ai∈{0,1,2},k∈N)c_i=3k+a_i(a_i\in\{0,1,2\},k\ ...
动态DP
把某些简单的树形DP改成带修改的，就变得十分不可做，便需要使用「动态DP」。“动态”顾名思义就是带修改的呗。
【模板】“动态 DP”&动态树分治
luogu-P4719 ：nnn 个点的树，每个点有权值，qqq 次询问，每次修改一个点的权值后求最大权独立集。
1≤n,q≤1051\le n,q \le 10^5
1≤n,q≤105
不考虑修改就是一个简单的DP问题：
设 fu,1f_{u,1}fu,1 表 uuu 子树中选择 uuu 点的最大权独立集，fu,0f_{u,0}fu,0 表不选 uuu 的最大权独立集，原来的转移方程：
fu,0=∑v∈son(u)max(fv,0,fv,1)f_{u,0}=\sum_{v\in son(u)} \max\big(f_{v,0},f_{v,1}\big)
fu,0=v∈son(u)∑max(fv,0,fv,1)
fu,1=au+∑v∈son(u)fv,0f_{u,1} =a_u+\sum_{v\in son(u)} f_{v,0}
fu,1=au+v∈son(u)∑fv,0
上式十分繁琐，我们简化一下：对树进行 ...
POI2014 - HOT Hotels
长链剖分优化树形DP板题。
luogu-P5905
给你一颗 nnn 个点的树，求有多少点对 (i,j,k)(i,j,k)(i,j,k) 满足 i,j,ki,j,ki,j,k 两两距离相等。
题解
u,v,wu,v,wu,v,w 两两距离相等只有两种情况，（1） ccc 是 u,v,wu,v,wu,v,w 三点的 LCA\mathrm{LCA}LCA 且 u,v,wu,v,wu,v,w 到 ccc 的距离一样。（2）ccc 是 u,vu,vu,v 的 LCA\mathrm{LCA}LCA 且 www 在 ccc 的子树外，u,v,wu,v,wu,v,w 到 ccc 距离相等。
考虑暴力 DP，设 f(u,i)f(u,i)f(u,i) 表示 uuu 的子树中到 uuu 距离为 iii 的点的个数， g(u,i)g(u,i)g(u,i) 表示 uuu 子树中存在多少点对 (v,w)(v,w)(v,w) （记 c=LCA(v,w)c=\mathrm{LCA}(v,w)c=LCA(v,w)）满足 dis(v,c)=dis(w,c)=dis(u,c)+i\mathrm{dis}(v,c)=\ ...
莫队二次离线
引入
长度为 nnn 的序列 aaa ，有 nnn 次询问（这里假设序列长度与询问次数同阶），每次询问 [l,r][l,r][l,r] 中满足某种条件的点对数量。
分析
区间 [l,r][l,r][l,r] 中与 xxx 构成关键对个数为 f([l,r],x)f([l,r],x)f([l,r],x) ，考虑右端点从 rrr 到 r′r'r′ 答案变化：
f([l,r],r+1)+f([l,r+1],r+2)+⋯+f([l,r′−1],r′)f([l,r],r+1)+f([l,r+1],r+2)+\dots+f([l,r'-1],r')
f([l,r],r+1)+f([l,r+1],r+2)+⋯+f([l,r′−1],r′)
显然有 f([l,r],x)=f([1,r],x)−f([1,l−1],x)f([l,r],x)=f([1,r],x)-f([1,l-1],x)f([l,r],x)=f([1,r],x)−f([1,l−1],x) ，那么：
∑i=rr′−1f([1,i],i+1)−∑i=rr′−1f([1,l−1],i+1)\sum_{i=r}^{r& ...
多项式学习笔记
多项式学习笔记…
多项式求逆
给定一个多项式 g(x)g(x)g(x) ，求一个多项式 f(x)f(x)f(x) 满足：
f(x)∗g(x)≡1(modxn)f(x)\ast g(x)\equiv1 \pmod {x^n}
f(x)∗g(x)≡1(modxn)
也记作 f(x)≡g−1(x)(modxn)f(x)\equiv g^{-1}(x)\pmod{x^n}f(x)≡g−1(x)(modxn)。
令 f∗(x)≡g−1(x)(modxn/2)f_\ast(x)\equiv g^{-1}(x)\pmod {x^{n/2}}f∗(x)≡g−1(x)(modxn/2)：
f∗(x)≡f(x)(modxn/2)f∗(x)−f(x)≡0(modxn/2)(f∗(x)−f(x))2≡0(modxn)f∗2(x)−2f∗(x)f(x)+f2(x)≡0(modxn)f∗2(x)g(x)−2f∗(x)+f(x)≡0(modxn)\begin{aligned}
f_\ast(x)&\equiv f(x) &\pmod{x^{n/2}}\\
f_\ast(x)- f(x)&\ ...
斯特林数学习笔记
蒟蒻的斯特林数笔记整理，未完待续。
相关公式
二项式定理
(a+b)n=∑k=0n(nk) akbn−k(a+b)^n =\sum_{k=0}^n \binom{n}{k} \,a^kb^{n-k}
(a+b)n=k=0∑n(kn)akbn−k
二项式反演
fn=∑i=0n(−1)i(ni)gi ⟺ gn=∑i=0n(−1)i(ni)fif_n=\sum_{i=0}^n (-1)^i \binom{n}{i} g_i \iff g_n=\sum_{i=0}^n (-1)^i \binom{n}{i} f_i
fn=i=0∑n(−1)i(in)gi⟺gn=i=0∑n(−1)i(in)fi
fn=∑i=0n(ni)gi ⟺ gn=∑i=0n(−1)n−i(ni)fif_n=\sum_{i=0}^n \binom{n}{i} g_i \iff g_n=\sum_{i=0}^n (-1)^{n-i}\binom{n}{i}f_i
fn=i=0∑n(in)gi⟺gn=i=0∑n(−1)n−i(in)fi
斯特林数的一些恒等式
{nm}=1m!∑k=0 ...
快速莫比乌斯/沃尔什变换 (FMT/FWT)
我们已知可以用 FFT 求加法卷积 Ci=∑j+k=iAj⋅BkC_i=\sum_{j+k=i}A_j\cdot B_kCi=∑j+k=iAj⋅Bk。
但形如 Ci=∑j⨁k=iAj⋅BkC_i=\sum_{j\bigoplus k=i}A_j\cdot B_kCi=∑j⨁k=iAj⋅Bk (其中 ⨁\bigoplus⨁ 为一个位运算符) 这样的位运算卷积，FFT 便束手无策。于是就要用到 「快速莫比乌斯变换」 FMT / 「快速沃尔什变换」 FWT 。
快速莫比乌斯变换（FMT）
与运算
Ci=∑i=j&kAj⋅BkC_i=\sum_{i=j\&k} A_j\cdot B_k
Ci=i=j&k∑Aj⋅Bk
定义变换：
FMT(A)i=∑j&i=iAj\mathrm{FMT}(A)_i=\sum_{j\&i=i} A_j\\
FMT(A)i=j&i=i∑Aj
这里可以把 i,ji,ji,j 看作集合（二进制下为一表示该位有，为零表该位无），FMT(A)i\mathrm{FMT}(A)_iFMT(A)i 就 ...
Link Cut Tree 总结
维护一颗森林，支持断边/连边，维护链上信息、连通性等。
主要思想是实链剖分，有虚边和实边，一些实边构成实链并由一颗 Splay 维护，Splay 根结点指向链顶的父亲，这条是虚边：认父不认子。这样一陀构成了若干个辅助树，辅助树有且仅有一个点没父亲，改点为辅助树的根。
写代码时注意事项
与普通 Splay 写法不同，Rotate 中先判断是否到根：
1234567inline void Rotate(int x) { int y=f[x],z=f[y],k=Get(x); if(!IsRoot(y)) ch[z][Get(y)]=x; // 注意这个 IsRoot(y) 放在最前面 ch[y][k]=ch[x][k^1]; f[ch[x][k^1]]=y; ch[x][k^1]=y; f[y]=x; f[x]=z; PushUp(y); PushUp(x);}
Splay 前要 Updata 将所有标记从根到下依次下传：
1234567891011void Updata(int x) { if(!IsRoot(x ...
原根简记
定义
阶：对于 a,m∈N∗,gcd(a,m)=1a,m\in \mathbf{N^{\ast}},\gcd(a,m)=1a,m∈N∗,gcd(a,m)=1 若 nnn 为最小的正整数满足：
an≡1(modm)a^n\equiv 1\pmod{m}
an≡1(modm)
称 nnn 为 aaa 模 mmm 的阶，记作 δm(a)\delta_m (a)δm(a) 。
显然若 an≡1(modm)a^n \equiv 1\pmod{m}an≡1(modm) ，则 δm(a)∣n\delta_m(a)\mid nδm(a)∣n
原根：g,m∈N∗g,m\in \mathbf{N^{\ast}}g,m∈N∗ 。若 gcd(g,m)=1\gcd(g,m)=1gcd(g,m)=1 且 δm(g)=φ(m)\delta_m(g)=\varphi(m)δm(g)=φ(m) 则称 ggg 为模 mmm 的原根。
性质 1
设 m,a,b∈N∗,gcd(a,m)=gcd(b,m)=1m,a,b\in \mathbf{N}^{\ast},\gcd(a,m)=\gcd(b,m)=1m,a, ...