分类 题解 下的文章

定理:确定分块大小后,至多只有一种划分方案。

暴力 DP

DFS 自底向上计算,用 dp_u 表示到 u 为止,未被分块的节点个数。

每次需要重新枚举块的大小,时间复杂度为 O(n \cdot \sigma(n)) ,会获得 TLE 的好成绩。

巧妙的优化

有个显然的事情就是每个点只能属于一个联通块。

也就是说,前面我们统计的那个 dp_u ,在做到 u 这个点时,要么把自己和子树未被分配的点分到同一个块内,要么就留着自己等着之后配。也就是说,每个联通块的最高点(深度最浅点)一定满足其子树大小是当前块大小 size 的倍数。

可以证明如果以 size 为大小分块有一种划分方案,那么至少存在 n / size 个点的子树大小是 size 的倍数,反之亦然。

我们可以直接统计下每个点的子树大小放在桶里,然后枚举下分块大小去扫描。复杂度显然低于调和级数的复杂度,故上届为 O(n \log n) ,可以通过此题。

READ MORE

注意到其实只有这 4 种骨牌是实际有效的

把原来的题意转化为这样:我们可以往角落依次里堆骨牌,可以放当且仅当其每个格子的左边和右边都被填满或是边界,最后要堆成一个 n \times m 的矩形。

把轮廓线提出来,一段自下而上走的记为 0 ,自左向右走的记为 1 。显然一开始为 n 个 0 连着 m 个 1 ,最后要变成 m 个 1 连着 n 个 0 。

考虑到四种图形对应的变换如下

before transformation after transformation image
0001 1000
0011 1010
0101 1100
0111 1110

发现中间的 2 个二进制位都是固定的,变化的只有第四位的 1 跑到了第一位去。

于是我们又可以转换题意,每次可以选择一个 1 ,然后把它向前移 3 格。分模 3 意义下讨论,每一部分就变成了杨氏矩阵计数,可以用钩子公式解决。

定义杨表的钩子为在这个格正下方和正右方的格子个数。钩子公式对于由 n 个格子组成的杨表,给其标号的方案数为 n! 除以每个格子的钩子大小 + 1 。

READ MORE

一个非常套路的 O(n^3) DP 就是用 f_{i, j} 表示做了前 i 项,其中最后一项是前 i 个中第 j 大的方案数,转移即

f_{i, j} = \begin{cases} \displaystyle \sum_{k=1}^{i-1} f_{i-1, k} & (s_{i - 1} = \textrm{<}) \\ \displaystyle \sum_{k=i}^j f_{i-1, k} & (s_{i - 1} = \textrm{>}) \\ \end{cases}

这个 DP 很难再进行优化,需要考虑别的算法。

考虑我们可以固定所有的 \textrm{>} ,并用容斥的方式来解决 \textrm{<} 。这样就变成了只有 \textrm{>}\neq 两种限制。可以看做排列被 \neq 分成了若干段,每段的排列的大小关系都是确定的,假设每段的大小分别为 a_{1 ... m} ,那么贡献即 \displaystyle \frac {n!} {\prod_{i=1}^m a_i} 。另外容斥系数只与硬点了几个 \textrm{>} 有关,可以和组合数放在一起 DP 。具体为

dp_n = \begin{cases} 1 & (n = 0) \\ \displaystyle \sum_{j=0}^{i-1} [j = 0 \textrm{ or } s_j = \textrm{<}] (-1)^{cnt_{i-1} - cnt_j} \frac {dp_{j}} {(i - j)!} & (n > 0) \\ \end{cases}

注意到的这个式子非常类似于分治 NTT 的形式,可以在 O\left(n \log^2 n\right) 的时间复杂度内解决。

READ MORE

官方题解是什么神仙东西看啊看不懂的。

Link

考虑我们维护一个分数类 (x, y) 表示 \frac x y 。假设 f(a_1, a_2, ..., a_n) = \frac x y 那么 f(a_0, a_1, a_2, ..., a_n) = \frac {a_0 x + y} {x} 。可以考虑用矩阵来维护转移。

定义将 (x, y)(a x + y, x) 的转移为

\left[\begin{matrix} a & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} x \\ y \\ \end{matrix}\right] = \left[\begin{matrix} ax + y \\ x \end{matrix}\right]

反之,从 (ax + y, x)(x, y) 的转移为

\left[\begin{matrix} 0 & 1 \\ 1 & -a \\ \end{matrix}\right] \left[\begin{matrix} ax + y \\ x \\ \end{matrix}\right] = \left[\begin{matrix} x \\ y \\ \end{matrix}\right]

那么

\begin{aligned} Ans_{l, r} &= \left[\begin{matrix} a_l & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_{l + 1} & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \\ &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 1} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 2} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \end{aligned}

可以分别处理出前缀和

\begin{aligned} F_n &= \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_n & 1 \\ 1 & 0 \\ \end{matrix}\right] \\ G_n &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n - 1} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \end{aligned}

READ MORE

\clubsuit 是 OI 国马拉松协会的会长。有一天,他打算举办全国青少年马拉松奥林匹克联赛(National Olympiad in Marathon in Provinces, NOMP),于是准备在 OI 国中修建一条赛道。

OI 国有 n (n \leq 5 \times 10^4) 个城市,一共有 n - 1 条道路将它们连通。也就是说,OI 国的结构是一棵树。

\clubsuit 会选择一个城市作为起点,再选择一个城市作为终点,这样赛道的长度就等于起点到终点路径上的边数。由于 OI 国的群众非常懒,所以赛道长为 0 也是允许的。

由于一些特殊原因,赛道的终点只能是一些特定的城市,而赛道的起点可以是任意一个城市。

现在小 \clubsuit 想知道:对于每个城市,如果选择它作为起点,那么赛道的长度有几种可能的取值?

READ MORE

给定 n (n \leq 100) 和长度为 n 的数组 \{a_i (a_i \leq 10^9)\} _{i=1}^n ,求满足 \forall i \in [1, n], c_i | b_i, b_i | a_i 并且 \prod_{i=1}^n c_i^2 \leq \prod_{i=1}^n b_i\{b_i\}_{i=1}^n\{c_i\}_{i=1}^n 的方案数。

假设 B = \prod_{i=1}^n b_i, C = \prod_{i=1}^n c_i^2 ,易证 C < B 的方案与 C > B 的方案是相同的,那么我们可以算出总共的方案加上等于的方案再除以二即可。

考虑等于的方案,这样即可把每个质因数分开考虑,相当于做个背包取第 0 项;

考虑总共的方案,对于质因数 xa_i 中出现了 k 次,贡献为 \frac 1 2 (k + 1) (k + 2)

READ MORE

傻逼题,CF 的数据是假的,不开 std::multiset 都可以过。

发现我们直接缩成一棵广义圆方树然后进行维护。修改点权的时候如果我们暴力修改圆点周围的方点显然可能挂掉,但是如果我们的方点只存圆方树上孩子的信息,那么就只用更新 O(1) 次了,这样的话在求 u \rightarrow v 的路径的时候判断一下 LCA 是不是方点即可。时间复杂度 O(n \log^2 n)

READ MORE

定义 s(x, y) 为将 xy 进行不进位加法的结果,求对于 a_{1 \dots n} 依次选出 n 个可以重复的数 b_{1 \dots n} ,求 \forall i \in [1, n] , s(b_1, b_2, b_3, \dots b_n) = i 的方案数目。n, a_i \leq 10^5 ,对 2^{58} 取模。

READ MORE

首先我们需要理解普通的 FWT 即给一个向量左乘一个矩阵进行转移,这在 k 进制下同样适用。用 w(i,j) 表示 \operatorname{fwt} 矩阵的第 i 行第 j 项。

对于给定的两个数列 ABC 是他们 k 进制下异或卷积的结果,即

\sum_{i \oplus j = k} A_i \times B_j = C_k

显然 FWT 还需要我们满足一个性质,即

\begin{aligned} \operatorname{fwt}(A)[x] \times \operatorname{fwt}(B)[x] &= \operatorname{fwt}(C)[x] \\ \sum_{i=0}^n w(x, i) A_i \sum_{j=0}^n w(x, j) B_j &= \sum_{k=0}^n w(x, k) C_k \end{aligned}

为了方便计算,我们希望能够构造出这样的 w 使得

\sum_{i \oplus j = k} w(x, i) A_i \times w(x, j) B_j = w(x, k) C_k

如果有

\forall i \oplus j = k, w(x, i) \times w(x, j) = w(x, k)

显然这就是个合法的 k 进制 \operatorname{fwt} 变换。

我们只构造一个满足 \forall i \oplus j = k, w(x, i) \times w(x, j) = w(x, k) 的矩阵 T 即可。

READ MORE

对于一个 1 \cdots n (n \leq 5 \times 10^5) 的排列 p_{1 \cdots n} ,定义 next_i 为第一个 j 满足 i < j, p_i < p_j ,如果不存在这样的 j ,则 next_i = n + 1 。给定一个缺失若干位的 next 数组,求构造任一合法的 p 数组。

READ MORE