Counting Arrays 题解
Counting Arrays题意给定数 $x,y$ 求序列 $a_y$ 的个数使得 $\prod_{i=1}^ya_i=x$。
Solution前置要将 $n$ 个完全一样的小球放进 $m$ 个盒子里面，要求不能有空盒子，就可以在 $n-1$ 个缝隙中插入 $m-1$ 个板子将 $n$ 分成 $m$ 份，于是容易得到方案数为 $\binom{n-1}{m-1}$。
但如果每个盒子中可以为空，就可以再加入 $m$ 个小球使得每个盒子必然被分到一个，然后在这 $n+m$ 个小球中插入 $m-1$ 块板子，于是最后答案就变成 $\binom{n+m-1}{m-1}$.
正文设 $x=\prod_{i=1}^kp_i^{\alpha_i}$，那么我们可以将这 $\sum\alpha_i$ 个质因数扔给 $y$ 个盒子，注意到这些质因子可能不同，因此不能整体使用插板法求方案数，而应该每个 $\alpha_i$ 分别做一次插板再乘起来。即答案为：
$$\prod \binom{\alpha_i+y-1}{y-1}$$
但注意到 $a_i$ 可以为负数，这样 ...
莫比乌斯反演
莫比乌斯反演反演引入假如对于 $f$ 有线性变换：
$$\begin{cases}F(1) = f(1)\ F(2) = f(1) + f(2)\ F(3) = f(1) + f(3)\ \vdots\F(n) = \sum\limits_{d\mid n}f(d)\end{cases}$$
我们想要知道 $F$ 反推 $f$，那么我们就需要一种运算叫做 反演。
同样地，我们举几个例子：
$$\begin{cases}f(1) = F(1)\ f(2) = F(2) - F(1)\ f(3) = F(3) - F(1)\ f(4) = F(4) - F(2)\ \vdots\ f(n) = \sum\limits_{d\mid n} \mu(\frac{n}{d})F(d)\end{cases}$$
其中，$\mu(n)$ 是一个数论函数，它代表着 $f(n)$ 的系数，可以的取值有 $1,0,-1$。
引入函数莫比乌斯函数定义1$$\mu(x)=\begin{cases}1, & ...
P1445 [Violet] 樱花 题解
P1445 [Violet] 樱花 题解题面给定正整数 $n$，求有多少组正整数有序数对 $(x,y)$ 满足 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$。
Solution拆式子观察式子 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$，同分后移项得到 $x\times y-n!\times (x+y)=0$，注意到这个式子中既含有 $x$ 与 $y$ 的乘积又含有它们的和，想到韦达定理，因此两边添加二次项 $(n!)^2$，然后因式分解得到：
$$(n!-x)(n!-y)=(n!)^2$$
对于任意一个 $x,y$ 满足给定条件的，一定对应着一种 $(n!-x)(n!-y)$ 的乘积方式，也就一定对应着 $(n!)^2$ 的一种分解方式。即每一种 $a,b\in \N$ 使得 $a\times b=(n!)^2$，就对应着唯一一组 $x,y$ 满足 $x=n!-a, y=n!-b$，也就对应着一组解。而行相对应的，一个 $a$ 就能得到唯一一个 $b& ...
P3557 题解
P3557 题解Des给定一张无向图，其中有 $n$ 个点 $m$ 条边，保证存在一个长度为 $k$ 的序列 $p_k$ 使得标记 $p_k$ 即 $p_k$ 一步能够到达的地方之后，所有的点都被标记。现在要求标记两步之内能够到达的点，求一种构造的方法使得所有点被标记。
Sol首先摆出结论：
对于一张图，我们计 vis[x] 表示节点 $x$ 的标记情况。每一次更新的时候，我们找到一个 $x$ 使得 vis[x]==false，然后标记所有 $x$ 两步之内能够到达的点，最后统计一下我们进行了多少次操作即可。
下面我们来 证明这个 显而易见 的结论：
首先，对于原图，我们知道，对于任意一个点 $x$，总存在 $i\in [1,k]$ 使得 $\operatorname{dis}(x,p_i)=1$ 或 $x=p_i$。
如果 $\operatorname{dis}(x,p_i)=1$，则我们在这里标记一定会在距离为 $1$ 的地方标记到 $p_i$，进而标记 $p_i$ 原来标记到的点。这样显然不劣。
如果 $x=p_i$，那么同样地，$x ...
Tree 题解
Tree (CF1111E)Des给定一棵树和若干次询问。每次询问有若干个数，前三个为 $k,m,r$ 分别表示节点数量，分组数量和根节点。即选中树上的 $k$ 个节点，在 $r$ 为根的情况下至多分成 $m$ 组有多少种分法，要求每个组内不能出现祖先关系。
其中 $\sum k\le 10^5, m\le 300$。
Sol是不是一眼虚树，但其实完全没必要。考虑动态规划。我们发现一个点能分到哪几个组里只与它有多少个关键节点祖先有关。因此，我们可以假设我们已经知道了它有多少个祖先，并且都做完了这些祖先的动态规划，然后试着转移当前节点。
因为 $m$ 很小，所以我们完全可以设成二维的状态 $f_{i,j}$ 表示前 $i$ 个点分成 $j$ 组的方案数。那么一个点可以分到原来的组里面，也可以自己一个组。而它不能分到祖先在的组里面。因此，我们设 $s(u)$ 表示 $u$ 有多少个关键节点祖先，那么很容易得到转移方程：
$$f_{i,j} = \max{ j - s(i), 0}\times f_{i-1, j} + f_{i-1, j-1}$$
然后就可以考虑如何先计算祖先。我 ...
平衡树
二叉搜索树指针我一般写二叉搜索树/平衡树的时候习惯用指针来写。它可以做到纯动态内存，但是同样的，写的时候会增加很多不必要的麻烦。比如说每次需要判断当前的指针是不是 null。下面介绍一些指针需要用到的基本操作：
定义很常见的一个错误的定义方式是：
1node* ls, rs;
这里的 * 是修饰 ls 的，而非 node。因此，定义的时候应写成：
1node *ls, *rs;
或者
1node *son[2];
调用对于结构体
1234struct node{ node *son[2]; int siz, cnt, val, key;};
调用 root 中的 val 应写成 root->val 而非 root.val，一般的，它也可以嵌套使用，比如 root->son[0]->siz。
判空在 pointer 类型中，判空的方法是 root == nullptr，或者 root == NULL。我习惯性写上：
1#define null nullptr
来简化代码。
新建指针因为要做到完全动态，所以内存就需要不断 ...
树上染色 题解
F - 树上染色Des给定一棵树，要求在树上把 $m$ 个点染成黑色，并有价值函数
$$v(E’) = \sum_{v_1,v_2\in E’} dis(v_1,v_2) + \sum_{v_1,v_2\in E-E’} dis(v_1,v_2)$$
求一种染色方式使得最大化 $v(E’)$。
Sol仍然考虑动态规划。
$f_{u,k}$ 表示 $u$ 子树内选择 $k$ 个 对答案的贡献。考虑这和 $f_{u,k}$ 表示 $u$ 子树内选择 $k$ 个 的价值 有什么不同。
对于答案的贡献，我们是默认在 $u$ 子树之外已经选择了 $m-k$ 个其他的黑色节点的，因此对于边 $u\to v$，若有 $v$ 子树内已经选择了 $k$ 个，那么边 $u\to v$ 经过的次数就是 $k\times(m-k)$ 次，因此对答案的贡献就是 $w\times k\times (m-k)$。同理可以计算得到白点的贡献。
而价值指的是 $u$ 子树内选择 $k$ 个，而 $v$ 子树内选择 $k’$ 个的贡献，这是不好被统计的。
由第一个设的状态，我们有转移方程：
$$f_{u,j} ...
Trailing Loves 题解
Trailing Loves题意给定一个数 $n$ 求 $n!$ 在 $b$ 进制下末尾 0 的个数。
Solution很容易想到的是 $n!$ 中有多少个因子 $b$ 就能在末尾产生多少个 0。那么假设
$$b=\prod_{i=1}^{k} p_i^{\alpha_i}，n!=\prod_{j=1}^{m} p_j^{\beta_j}$$
那么我们就只需要一一对应 $b$ 含有的质因子，取
$$\min_{i=1}^k{\frac{\beta_i}{\alpha_i}}$$
为答案即可。
其中 $n!$ 的因子 $p_j$ 的指数可以表示为
$$\beta_j=\sum_{i=1}^{p_i\le n}\frac{n}{p^i}$$
CODE123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;const int ...
Untitled
6.15 题解A - 星际蛋糕推销Des你有 $n$ 个数，我们希望这 $n$ 个数都是奇数。因此，我们每一次会对于最左边的一个偶数进行减半操作，即把 $a_i$ 变成两个 $\frac{a_i}{2}$ 并放在原位置上。完成操作后求有 $m$ 个询问求第 $i$ 个位置是什么。
Sol显然，若将 $a_i$ 质因数分解，则有：
$$a_i = \prod_{p\in \mathcal{P}} p_i^{\alpha_i}$$
其中 $p_1=2$，因此它会被切 $2^{\alpha_1}$ 次。这样，我们就能够知道每一个数会被分成多少个数，维护一个前缀和表示每个数产生的数截止到哪里，然后每一次二分查找答案即可。复杂度 $O(n\log n)$。
B - 狡猾的商人Des给定 $m$ 次询问并告诉你答案。具体的，每一次询问形如 $l,r,s$，表示 $\sum\limits_{i=l}^ra_i=s$。你需要判断存不存在数列 $a_i$ 满足条件。
Sol让我们把询问写成前缀和的形式。具体的，对于询问 $l,r,s$，我们有 $s_r-s_{l- ...
Untitled
6.13 题解D - Glass CarvingDes有一个 $w\times h$ 的玻璃每一次可以在 横/竖 方向上某一个位置切一刀，求最后的最大的矩形面积。
Sol首先，一个显而易见的结论是，对于横方向和纵方向，我们都取最大值，于是答案就是它们的乘积。
考虑如何维护横方向和纵方向的最大值。
因为切刀是在 $(x,x+1)$ 的中间切的，这很不好，因此我们把矩形变成 $(2w-1)\times(2h-1)$ 大小，其中对于 $\forall i \in [1,n)$，第 $2i$ 个位置表示原来 $(i,i+1)$ 的 缝隙。这样，我们在修改的时候就可以精确地找到它的位置。
于是我们使用两只线段树，分别统计横向和纵向的切割情况。初始线段树都设成 $1$，对于一次修改 $x$，我们把 $2x$ 这个地方修改成 $-\infty$，于是最长的长度就是整只线段树的最大子段和。记 $ans$ 是最大子段和，那么它还原回去的最大长度就是 $\frac{ans+1}{2}$。
当然，你也可以发明一个最长连续 $1$ 的个数，这个东西和最大子段和很像，也不是太难写 （我就是这么写的$Q ...