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

不知道有没有人发现这个博客的更新频率在逐渐减少,有些时候想更新篇博文却没有实力,冷静了下不如断了念想,挂个停更通知,也算安慰下自己的虚荣心吧。

READ MORE

Macbook Pro 买来都快一年了,可以由于自己比较咕加上大部分用电脑的时间都在学校就没想去外接显示器。

还在用 Surface Pro 的时候入过一个比较入门的 4k 显示器,最近捣鼓捣鼓终于给用上了。

READ MORE

之前利用 aliyun 的学生机作为跳板机连几台在学校的机子,可是每次输入长长的一串命令总感觉比较麻烦,加上最近再写一个小工具来方便自己维护服务器,如果考虑跳板的命令又会比较麻烦,就去简单学习了一下如何通过配置 ssh config 来达到目的。

READ MORE

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

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

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

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

READ MORE

先考虑 K = 0 的情况。我们显然需要将 x 轴和 y 轴分开考虑。但是考虑到 x 轴和 y 轴不能同时只增长 0 ,这个就可以二项式反演了。定义 f_i 表示恰好出现 i(0, 0) 的方案数,g_i 表示至少出现 i(0, 0) 的方案数,也就是题目给我们的 R 只能用 R - i 次。显然

\binom R k g_k = \sum_{i=k}^R \binom i k f_i \Leftrightarrow f_k = \sum_{i=k}^R (-1)^{k-i} \binom i k \binom R i g_i

ans = f_0 ,我们只需要求出 \{g_i\}_{i=0}^R 即可。

这个东西显然可以直接卷一下 \forall k \in [0, R] ,\; \left( \sum_{i=0}^M x^i \right)^k ,然而这个东西显然会让你 get TLE ,考虑有没有什么优秀的方法。

再次考虑容斥,用 f'_i 表示恰好有 i 步超出限制,g'_i 表示至少 i 步超出限制。显然

g'_k = \sum_{i=k}^R \binom i k f'_i \Leftrightarrow f'_k = \sum_{i=k}^R (-1)^{k-i} \binom i k g;_i

g_iR = i 时的 f'_0 。这个 g'_i 就比较好求了,可以插板法,我们硬点一些箱子至少选 M + 1 ,另一些至少选 0 个。7

以上部分的时间复杂度是 O(R^2) 的,也可以通过 60\% 的数据。

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