几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

你现在要洗 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

类似于「THUPC2019 找树」那题类似,我们给矩阵每个存个 x^{a_{i, j}} 的多项式。注意到题目要求我们求的东西非常类似于求一个行列式,但是于行列式不同的是,题目没有 (-1)^{\textrm{逆序对个数}} 这个系数。

考虑到最后我们只需要统计答案的幂级数这位有没有系数,而不关心具体是多少。我们可以在一开始随机一个系数,这样随着加加减减很难被消成 0 。最后统计下答案即可。

需要 3 进制 FWT ,可以模 10^9 + 9\omega_3 = 115381398, \omega_3^2 = 884618610 \pmod {10^9 + 9}

READ MORE