memset0's Notebook

给定两个 01 串 X, Y，其中可以包含若干问号表示这一位可以是 0 也可以是 1。求有多少对这样的二元字符串 (S, T) 满足 |S|, |T| \leq n 且将 X, Y 的每个 0 1 替换为 S, T 后两个串相等。

|X|, |Y|, n \leq 3 \times 10^5。

Link: https://codeforces.com/problemset/problem/794/G

配置 SSH config 使用跳板机连接

2019-08-10
杂记
1 comment

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

Min_25 筛重新学习笔记

2019-07-30
算法
8 comments

大半年以前被集训队大爷 CMXRYNP 教育过一次，然而由于本人记忆力太差所以只能重新学习一遍。

LOJ6035 「雅礼集训 2017 Day4」洗衣服

2019-07-23
口胡
6 comments

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

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

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

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

LOJ6374 「SDWC2018 Day1」网格

2019-07-21
口胡
2 comments

先考虑 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_i 即 R = i 时的 f'_0 。这个 g'_i 就比较好求了，可以插板法，我们硬点一些箱子至少选 M + 1 ，另一些至少选 0 个。7

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

LOJ6051 「雅礼集训 2017 Day11」PATH

2019-07-20
题解
0 comment

给定 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。