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

你现在要洗 l 件衣服。你有 n 台洗衣机和 m 台烘干机。由于你的机器非常的小,因此你每次只能洗涤(烘干)一件衣服。

i 台洗衣机洗一件衣服需要 w_i 分钟,第 i 台烘干机烘干一件衣服需要 d_i 分钟。

请问把所有衣服洗干净并烘干,最少需要多少时间?假设衣服在机器间转移不需要时间,并且洗完的衣服可以过一会再烘干。

l \leq 10 ^ 6, n, m \leq 10 ^ 5

READ MORE

一枚棋子要从 (0,0) 跳到 (T_x,T_y)。每一步只能向右上方跳,且横坐标变化不能超过 M_x,纵坐标变化不能超过 M_y,每一次跳跃不能停留在原地。

K 个向量是非法的,这些向量形如 (k_i,k_i) ,会在读入中给出。也就是说,每一步 x,y 的增量不能同时等于 k_i所有的 k_i 都是 G 的倍数。

求从 (0,0),跳恰好 R 步到 (T_x,T_y) 的方案数。答案对 10^9+7 取模。

T,M \leq 10^6,\ R \leq 1000,\ 10000 \leq G \leq 50000,\ K \leq 50

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

假设 f_i 表示第 i 步恰好结束的概率,g_i 表示第 i 步还未结束的概率,h_{k, i} 表示第 i 步恰好结束并且以字符 k 结尾的概率。F(x), G(x), H(x) 分别是 \{f_i\}_{i=0}^\infty, \{g_i\}_{i=0}^\infty, \{h_i\}_{i=0}^\infty 的普通生成函数。

显然我们知道 F(1) = 1 ,要求 E = F'(1)

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