当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

分类 题解 下的文章

给定长度为 n 的序列 \{a_i\}_{i=1}^n,有 q 组询问 [l,r],定义三元组 (A,B,C)

  • 是合法的当且仅当 L \le A < B < C \le R(B-A) \leq (C-B)
  • 的权值为 a_A + a_B + a_C

求给定区间内三元组的最大权值。 n ,q \leq 5 \times 10^5,\ a_i \leq 10^9

READ MORE

给定 n\{a_i\},满足 a_0 \geq a_1 \geq \cdots \geq a_{n - 1} \geq 0,求出在 n 维空间中从 (0, 0, \ldots, 0) 走到 (a_0, a_1, \ldots, a_{n - 1}),每一步使某一维坐标增加 1 的方案中随机选出一种,满足经过的所有点 (x_0, x_1, \ldots, x_{n - 1}) 都满足 x_0 \geq x_1 \geq \cdots \geq x_{n - 1} 的概率,答案模 1004535809 输出。

n, a_i \leq 5\times 10^5

READ MORE

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

暴力 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

Solution1 - 二元生成函数

注意到比较难办的一个限制即每个数只能选一次,考虑 \forall \; i \in [1, n] 用一个二元生成函数 1 + y x^{a_i} 来表示。最后我们要求的即

\forall \; i , \; [y^k \cdot x^i] \prod_{\textrm{or}} 1 + y x^{a_i}

考虑对于给 F_i(x) = 1 + y x^{a_i} 做一次 or transformation 是什么

[x^k] \operatorname{FWT_{\textrm{or}}} (F_i(x)) = \begin{cases} 1 & (a_i \notin k) \\ 1 + y & (a_i \in k) \\ \end{cases}

把点值乘起来以后每一位就是 (1+y)^\theta ,显然我们只需要对于每一项求出 [x^k] (1+y)^\theta ,这其实就是 \binom \theta k

\theta 也是好求的,每一个 F_i(x) = 1 + y x^{a_i} 只会对答案贡献 1 ,且一定是在 a_i \in k 的位置。可以直接定义 G(x) = \sum_{i=0}^\infty x^i \sum_{j=1}^n [a_j = i] ,然后做一次高维前缀和。

求出 [y^k] \prod_{\textrm{or}} F_i(x) 后,事情就变得简单了起来,一遍 interverse or transformation 加上一遍 and transformation 直接带走。

Solution2 - 容斥

cnt_S = \sum_{i=1}^n [a_i \cup S = \emptyset] ,即与 S 没有交集的 a_i 个数。

考虑对于每一个询问 \operatorname{query}(S) 统计方案数。这相当于我们硬点了一个子集里的特性没有出现过,然后容斥。

显然

\operatorname{query}(S) = \sum_{T \in S} (-1)^{|T|} \binom {cnt_T} k

求出 cnt_S 后拿 (-1)^{|T|} \binom {cnt_T} {k} 来做一趟 or transformation 即可。

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

同时考虑点权和边权比较困难,如果可以把边权并到点权里,那么就可以直接贪心了。

注意到对于一条边的边权对答案的贡献

  • 如果两边都是黑点,对答案的贡献为 1 ,可以看做两个黑点分别为答案贡献了 \frac 1 2
  • 如果两边都是白点,对答案的贡献为 -1 ,可以看做两个白点分别为答案贡献了 - \frac 1 2
  • 如果一边是白点一边是黑点,贡献为 0 ,可以看做黑点为答案贡献了 \frac 1 2 的边权,白点为答案贡献了 - \frac 1 2 的贡献

这样话设置每个点的排序关键字为点权加上 \frac 1 2 的相邻边权和,按从大到小排序后奇数位为黑点,偶数位为白点即可。

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