树链剖分（decomposition）
定义一个树的一种树链剖分的权值为：所有 (u,v)(u≤v)(u,v)(u\le v)(u,v)(u≤v) 之间的经过轻边的个数的和。
定义一个树的最优树链剖分为权值最小的树链剖分。
给定 nnn 个点的树。
对于每一个节点 iii，求以 iii 为根的情况下的最优树链剖分的权值。
n≤105n\le 10^5n≤105。
显然的换根 DP，于是我们先考虑单次树形 DP 怎么求。
首先我们应该拆贡献：对于每一条边 (u,v)(u,v)(u,v)，其中 uuu 是 vvv 的父亲，那么共有 szv(n−szv)sz_v(n-sz_v)szv(n−szv) 个路径经过它。那么只要其不是重边，答案就要累加这个值。
于是我们定义 fxf_xfx 表示考虑 xxx 子树内的所有边的贡献的最小权值，则有：
fx=∑ufu+∑uszu(n−szu)−maxu{szu(n−szu}f_x=\sum_u f_u+\sum_u sz_u(n-sz_u)-\max_u\{sz_u(n-sz_u\}
fx=u∑fu+u∑szu(n−szu)−u ...
Expression
HDU2015。
有 nnn 个数和 n−1n-1n−1 的运算符。
每一次操作你可以选择相邻的两个数并将他们按照他们之间的运算符进行运算。
显然 n−1n-1n−1 次运算后这些数会变为一个。
求按每一种操作顺序操作之后，最终的数的和。对 109+710^9+7109+7 取模。
n≤500n\le 500n≤500。
显然有一个 O(n2)\mathcal{O}(n^2)O(n2) 的区间 DP：令 fi,jf_{i,j}fi,j 表示区间 [i,j][i,j][i,j] 的答案，那么有：
fi,j=∑i≤k<jopt(fi,k,fk+1,j)f_{i,j}=\sum_{i\le k<j}\operatorname{opt}(f_{i,k},f_{k+1,j})
fi,j=i≤k<j∑opt(fi,k,fk+1,j)
然后你就发现你 WA 了。
原因是这样的：fff 计算的是和。
举一个例子：不妨设 fi,kf_{i,k}fi,k 里面的所有数是 {1,2,3}\{1,2,3\}{1,2,3}，运算符是 +++，fk+1, ...
Rectangles
O(n2)\mathcal{O}(n^2)O(n2) 做法（嘲讽 Sam O(n2logn)\mathcal{O}(n^2\log n)O(n2logn)）。
HDU 2013。
给定 n,m,kn,m,kn,m,k 以及 kkk 个关键点 (Xi,Yi)(X_i,Y_i)(Xi,Yi)。求有多少个 1≤x1≤x2≤n,1≤y1≤y2≤m1\le x_1\le x_2\le n,1\le y_1\le y_2\le m1≤x1≤x2≤n,1≤y1≤y2≤m，满足矩形 (x1,y1)(x2,y2)(x_1,y_1)(x_2,y_2)(x1,y1)(x2,y2) 内部至少有一个关键点。
1≤n,m≤109,1≤k≤10001\le n,m\le 10^9,1\le k\le 10001≤n,m≤109,1≤k≤1000。
首先我们有一个错误的做法：
对于每一个关键点 (Xi,Yi)(X_i,Y_i)(Xi,Yi)，计算所有包含这个点的矩形个数，即 XiYi(n−Xi+1)(m−Yi+1)X_iY_i(n-X_i+1)(m-Y_i+1) ...
[JOIST 2024] 鱼 3 / Fish 3
[JOIST 2024] 鱼 3 / Fish 3。
定义一个序列 aaa 的权值 f(a)f(a)f(a) 为：
令 p=0p=0p=0。
重复执行以下操作，直到序列 aaa 单调不降：
p←p+1p\leftarrow p+1p←p+1。
选择一个 1≤x≤n1\le x\le n1≤x≤n，令 ax←ax−Da_x\leftarrow a_x-Dax←ax−D。
若 ppp 有限，则 f(a)=min{p}f(a)=\min\{p\}f(a)=min{p}；否则，f(a)=−1f(a)=-1f(a)=−1。
给定序列 aaa，多次询问，每次给出一个 l,rl,rl,r，求 f(a[l:r])f(a[l:r])f(a[l:r])。
n,m≤3×105n,m\le3\times10^5n,m≤3×105；ai,D≤1012a_i,D\le10^{12}ai,D≤1012。
神秘性质题。
首先考虑只有一个询问时的做法。此时我们有一个简单的贪心思路：aia_iai 的操作次数应该为：
max{0,⌈ai−mi ...
Top Trees 领先®
全局平衡二叉树
你要在 O(nlogn)\mathcal{O}(n\log n)O(nlogn) 的时间内解决：
给 1∼x1\sim x1∼x 路径上的点权 +1+1+1。
求 1∼x1\sim x1∼x 路径上的点权和。
最经典的解法当然是 O(log2n)\mathcal{O}(\log^2n)O(log2n) 的树链剖分，然而复杂度过劣，于是就有了全局平衡二叉树。
想一想树剖的做法有没有什么优化的空间：
给每一个重链单独开一个线段树，这样常熟更小。
对于每一个线段树，我们希望比较“重”的节点深度更小一点，因为在到达这个节点之前我们付出了更大的代价。
那么，我们可以在建立线段树的时候，不再从区间中点分治，而是带权分治——权值为 szx−szsonxsz_x-sz_{son_x}szx−szsonx，即其子树的“重量”。
那么我们从某一个节点往上跳，若经过轻边，则子树大小必然翻倍。若经过重边，由于带权分治，子树大小依然翻倍。
于是树高 O(logn)\mathcal{O}(\log n)O(logn)。
那么我们就完成了这一优化。
...
ABC478
没有 AK /ll
A. Grapes
nnn 个人 mmm 个糖。
对于 i=1∼mi=1\sim mi=1∼m，执行：
人类 (i−1) mod n+1(i-1)\bmod{n}+1(i−1)modn+1 的糖的数量 +1+1+1 。
求每个人最终的糖果数量。
n≤1000,m≤10000n\le 1000,m\le 10000n≤1000,m≤10000。
数学或者模拟，随便你怎么写。
数学的话就是 ⌊mn⌋+[i≤m mod n]\lfloor\frac{m}{n}\rfloor+[i\le m\bmod{n}]⌊nm⌋+[i≤mmodn]。
::::success[代码]
123456789#include <bits/stdc++.h>using namespace std;const int N=1001;int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)printf("%d\n",m/n+(i<=m%n)); ...
CF1093F Vasya and Array
CF1093F 加强版。
Niko 有一个长度为 nnn 的整数序列 aaa 以及两个整数 k,mk,\text{m}k,m，保证 ai∈[1,k]∪{−1}a_i\in[1,k]\cup\{-1\}ai∈[1,k]∪{−1}。
求有多少种将 aaa 中的 −1-1−1 替换为 [1,k][1,k][1,k] 中的整数的方式，使得 aaa 中不存在长度为 m\text{m}m 的连续相同区间。答案对 109+710^9+7109+7 取模。
n,k,m≤2×106n,k,m\le 2\times 10^6n,k,m≤2×106。
原版支持 O(nk)\mathcal{O}(nk)O(nk)，加强版只能 O(n)\mathcal{O}(n)O(n)。
先看简单版（虽然没有什么用处）：
定义 fi,jf_{i,j}fi,j 表示前 iii 个以 jjj 结尾的方案数，那么我们只需要枚举连续的 jjj 的个数就行：
fi,j=∑k(∑pfk,p)−fk,jf_{i,j}=\sum_k(\sum_p f_{k,p})-f_{k,j}
...
[ARC096E] Everything on It
称一个不可重集 aaa 合法当且仅当：
aaa 中仅含 [0,2n−1][0,2^n-1][0,2n−1] 中的数。
对于任意一个二进制位 0≤i<n0\le i<n0≤i<n，aaa 中至少有 222 个数满足其在这一二进制位为 111 。
计数合法的 aaa。
n≤3000n\le 3000n≤3000。对一个质数 mmm 取模。
先来基本的推式子：
Ans=∑a∏i=1n[count(a,i)≥2]=∑a∏i=1n1−[count(a,i)≤1]=∑a∏i=1n1−[count(a,i)=0]−[count(a,i)=1]\begin{aligned}
\text{Ans}&=\sum_a\prod_{i=1}^n[\operatorname{count}(a,i)\ge 2]\\
&=\sum_a\prod_{i=1}^n1-[\operatorname{count}(a,i)\le 1]\\
&=\sum_a\prod_{i=1}^n1-[\operatornam ...
[AGC058D] Yet Another ABC String
给定整数 AAA、BBB、CCC。请计算由 AAA 个 A、BBB 个 B、CCC 个 C 组成的字符串 SSS，满足以下所有条件的字符串个数，并将结果对 998244353998244353998244353 取模。
SSS 中包含的 A、B、C 的数量分别为 AAA、BBB、CCC。
SSS 中不包含 ABC、BCA、CAB 中的任意一个作为子串。
1≤A,B,C≤1061\le A,B,C\le 10^61≤A,B,C≤106。
令 A=0,B=1,C=2A=0,B=1,C=2A=0,B=1,C=2。
首先将限制写下来：
∑a∏i1−[ai+1≡ai+1][ai+1≡ai+2][ai+2+1≡ai]\sum_a\prod_i1-[a_i+1\equiv a_{i+1}][a_{i+1}\equiv a_{i+2}][a_{i+2}+1\equiv a_i]
a∑i∏1−[ai+1≡ai+1][ai+1≡ai+2][ai+2+1≡ai]
发现并不好处理。但是由于限制的形式特殊，即，若 [i, ...
[PA 2019 Final] 数图 / Grafy
我不会容斥。
求出 nnn 个节点的满足以下条件的有标号有向简单图的数量：
∀1≤i≤n\forall 1\le i\le n∀1≤i≤n，degout(i)=degin(i)=2\operatorname{deg_{out}}(i)=\operatorname{deg_{in}}(i)=2degout(i)=degin(i)=2。
这里，degout(u)\operatorname{deg_{out}}(u)degout(u) 指节点 uuu 的出度，degin(u)\operatorname{deg_{in}}(u)degin(u) 指节点 uuu 的入度。
你只需要输出答案对给定大素数 ppp 取模后的结果。
n≤500n\le 500n≤500。
首先，将图转化为一个邻链表存储。即改为计数 b[0⋯2n−1]b[0\cdots 2n-1]b[0⋯2n−1]，其中 b2ib_{2i}b2i 和 b2i+1b_{2i+1}b2i+1 表示 iii 的两条邻边。
考虑到顺序问题过于麻烦，考虑忽略顺序， ...
