求邀请函优先级，才发现错过了好难受啊QAQ
2019.7 月赛题解
Xiejiadong edited 3 年，2 月前
花絮
-
企业邮箱换成了网易的，受到了每天发送的限制，所以月赛邀请函只随机发出了 $2000$ 封。
-
由于 5月月赛难度失控被喷。所以这个月还是放了纯签，可能还不止一题。
-
幸好是 ICPC 赛制，本来预估的难度是 D 要简单于 B 的。
-
前一天晚上收到 blunt_axe 的题解，不得不感叹我们的题解过于简陋。
-
果然 blunt_axe 就算能做的少一题，也照样踩爆好多人啊。
| # | Tag | Idea | Developer | Tester |
|---|---|---|---|---|
| A | 线性基 高斯消元 | cs2017 Xiejiadong | Xiejiadong | Weaver_zhu |
| B | 简单数学 贪心 | Xiejiadong | Xiejiadong | Kilo_5723 oxx1108 |
| C | 数学 尺取法 | blunt_axe | Weaver_zhu Kilo_5723 | Kilo_5723 oxx1108 |
| D | 送分 签到 | Xiejiadong | Xiejiadong | Kilo_5723 |
| E | 树形DP | kblack | kblack | Xiejiadong |
Problem A
First Solved：PinkRabbit
考虑素因数分解。如果几个数乘起来是一个完全平方数，则其各个素因子幂次都是偶数。
一个区间 $(l, r)$ 任意取数乘起来得到完全平方数则等价于，一些表示素因子幂次奇偶性的二进制串异或起来是否为 $0$ 。于是可以考虑使用线性基解决问题。
对于本问题，如果答案为 $ans$，则需要求出最大的 $ans$ 使得 $(ans+1, n-1)$ 任意取数异或上 $n$ 的二进制串为 $0$ ( 因为 $n$ 是必须取得 )。
考虑线性基的部分，$10^6$ 以内的素数个数是 $10^5$ 数量级的，我们需要 $O(10^5)$ 长度的二进制串吗？实际上，$1000$ 以内的素数不超过 $200$ 个，而 $1000$ 以上的素因子，最多只有一个。
于是我们的线性基只是需要 $10^5$ 左右数量的 $200$ 位二进制串外加一个整数 ( 表示 $1000$ 以上的素数 )。
加入一个数的时间复杂度是 $O(200)$ 的，我们从大到小检测每次加入一个数后，是否有新的 $n$ 的素因子在线性基中可以被取到。
这样枚举每个 $ans \in [1, n]$ 是 $\mathcal{O}(200)$ 的。如果用 $bitset$ 实现二进制串，空间也是足够的。
Comments
Xiejiadong ：教练从《具体数学》作业题中找到了这道题目，问我范围能做到多大。然后好像和 OpenCup 的某场 A 题心灵相通了。不太能搜到题解，而且觉得很有意思就放出来了。
Xiejiadong ：为了不卡常，所以没有拉满，看起来复杂度多一个 log 也是能跑过去的。
Problem B
First Solved：DeaphetS
考虑如果有小朋友在 $x$ 天来了图书馆。
-
可能他是每间隔 $x-1$ 天来一次图书馆，于是所有日期为 $y$ 且满足 $y-1\equiv 0(mod\; x-1)$ 的日期都可以由他产生，故不再考虑这些天；
-
如果他不是每间隔 $x-1$ 天来一次图书馆，那么他的间隔只能更小，假设他的间隔为 $a$ ，一定有 $a|(x-1)$ ，这样一来，他一定在第 $a+1$ 天的时候来了图书馆，那个时候我们已经可以知道不用再对 $x$ 天考虑了，所以不可能存在这样的情况。
于是，我们只需要从小到大依次考虑没有被标记过（不用再考虑）的天数，并从标记他所能取消的天数就可以了。
这样有两种方式维护，一种是对每个天数判断他的约数是否已经存在，时间复杂度 $\mathcal{O}(n\sqrt{n})$ ；
也可以用类似于筛法求质数那样做，时间复杂度 $\mathcal{O}(nlogn)$ 。
可能需要特判 $n=1$ 的情况。
Problem C
First Solved：404 Not Found.
本题 Idea 由著名 OI 选手 blunt_axe 提供。
题目本是 OI 题，故有部分分设置，详细部分分设置和部分分题解请参照blunt-axe 的博客。
Solution by blunt_axe
首先进行初步的分析。不难发现可以将「星星会在时刻 $a_i + k \times b_i (k \in N)$ 闪烁」的条件替换成「星星会在时刻 $(a_i \bmod b_i) + k \times b_i (k \in N)$ 闪烁」，这不影响答案。这是因为如果在时刻 $x$ 选中的星星都会闪烁，那么在时刻 $x + 10^9 \times \text{lcm}(b_1, b_2, \cdots, b_n)$ 它们也都会闪烁。这样，我们就可以预先把输入进来的 $a_i$ 全部对 $b_i$ 取模。
然后发现这个题目本质是询问一个区间的线性同余方程组是否有解。也就是询问：
$$
\begin {cases}
x \equiv a_1 \pmod {b_1} \
x \equiv a_2 \pmod {b_2} \
\cdots \
x \equiv a_n \pmod {b_n}
\end {cases}
$$
是否有解。
注意到不能直接使用 ExCRT 的方法计算答案，因为答案可能很大。但是这题只需要我们判断方程组是否有解，所以无需算出答案。
可以证明：一个线性同余方程组有解当且仅当其中的任意两个方程形成的方程组都有解。原因是一个线性同余方程组的所有解一定可以写成满足「$x \equiv r_1 \pmod {p_1^{k_1}}, x \equiv r_2 \pmod {p_2^{k_2}}, \cdots$（$p$ 是素数）」这样一组的条件的任何数。如果一个方程组没有解，那么一定存在「$x \equiv r_1 \pmod {p_1^{k_1}}$，并且 $x \equiv r_2 \pmod {p_1^{k_1}}, $，其中 $r_1 \neq r_2$」这两个限制。而对于这两个限制，一定能找到两个方程，它们分别包含了两个限制的信息。也就是说，如果线性同余方程组无解，那么一定存在两个方程，它们组成的方程组无解。换句话说，如果任意两个方程形成的方程组都有解，则整个方程组一定有解。
我们暴力枚举每两个方程，判断它们是否矛盾即可。使用裴蜀定理即可证明它们不矛盾当且仅当 $\gcd(b_1, b_2)$ 整除 $a_1 - a_2$。时间复杂度 $\mathcal{O}(n + qn^2 \log b_i)$。
考虑优化算法。看到了 $\gcd$ 以后容易想到枚举因数。枚举因数 $d$，考虑所有 $b_i$ 是 $d$ 倍数的星星。如果所有 $a_i \bmod d$ 都相同的话，就没有矛盾。这样一次的复杂度是 $\mathcal{O}(b_i \log b_i)$ 的，但是由于我们只需要枚举 $d$ 是素数或素数的几次方的情况，复杂度可以降为 $\mathcal{O}(b_i \log \log b_i)$。于是总共的时间复杂度减少到 $\mathcal{O}(q(n + b_i \log \log b_i))$。
之前的算法似乎没什么前途，考虑换一种思路。
对于每组限制 $(a_i, b_i)$，我们将 $b_i$ 素因数分解：$b_i = \prod_{j} p_j^{k_j}$ 。然后，对于每一个 $p_j^{k_j}$，将其拆成 $k_j$ 个限制，模数分别等于 $p_j, p_j^2, \cdots, p_j^{k_j}$，余数等于 $a_i$ 对它们取模的结果。对于一组 $(a_i, b_i)$，我们最多会将其拆成 $\log b_i$ 组限制。实现素因数分解时可以使用线性筛。
拆分后的好处是什么呢？发现如果两个方程矛盾，那么从它们中一定可以各自选出一个限制，满足限制的模数相同，但余数不同。
这样我们就把问题转化成了：给定 $\mathcal{O}(n \log n)$ 组有序数对 $(a_i, b_i)$，每次询问一个区间内是否存在 $b_i$ 相同且 $a_i$ 不同的一组数对。
不难发现对于每一个点 $i$，一定存在一点 $p_i$ 使得以 $i$ 为右端点的区间 $[l, i]$ 中所有 $l \ge p_i$ 的答案都为 Yes，而 $l < p_i$ 的区间答案都为 No。考虑用 2 - pointers 预处理出 $p_i$。由于具体过程叙述起来较为复杂，请读者自行思考，也可以参考标程。
时间复杂度 $\mathcal{O}(n \log b_i + b_i)$。
Solution by Kilo_5723
尝试维护一个集合，保证其中所有星星都能同时闪烁。考虑何种情况下集合满足这个性质。
我们发现，对每一个质数 $p$，对所有的 $i$ 使得 $p \mid b_i$，需要让每一个 $a_i \; {\rm mod }\; p^{k_i}$ 互不冲突，其中 $p^{k_i}\mid b_i,p^{k_i+1}\nmid b_i$。而不冲突的定义为：令最大的 $p^{k_x}=P$，对应的 $a_x \; {\rm mod }\; P = MOD$，则对所有的 $i$ 都有 $a_i \; {\rm mod }\; p^{k_i} = MOD \; {\rm mod }\; p^{k_i}$。
利用这个性质，滑动窗口维护对每一个 $l$，最大的 $r$ 使得 $[l,r]$ 中的星星能同时闪烁。
Problem D
First Solved：blunt_axe
我们可以考虑以 $(0,0)$ 格子作为原点建立坐标系。
于是子矩阵就相当于限制了变量 $x$ 和 $y$ 的范围，对角线变成了直线 $y=x$ 和 $y=-x+(n-1)$ 。
问题变成了求给定的范围内的整点个数。
需要注意矩阵边长为奇数的时候，矩阵正中央的格子会被重复计算。
Problem E
First Solved：gyz_gyz
状态无非分为两种：理论状态（所有门元器件正常的时候的输出）、实际状态。
于是我们令 $f[i][x][y](x=0/1,y=0/1)$ 表示门元器件 $i$ 的理论输出 为 $x$ ，实际输出为 $y$ 的方案数。
理论和实际状态都为 $0$ 的是最好处理的，因为理论 $0$ 的状态只能是所有的输入为 $1$ 。
理论的状态为 $1$ ，实际状态为 $0$ ，那么对于理论状态只需要任意一个输入或者多个输入为 $0$ 即可。这个处理起来会有点麻烦，但是我们可以通过输入为 $0$ 或者 $1$ 的状态减去 输入全 $0$ 的状态快速得到。
理论的状态为 $0$ ，实际状态为 $1$ 的情况和上一种情况类似的处理。
而对于最后一类状态，即理论和实际都为 $1$ 的状态，我们通过所有的状态减去前面三个状态转移即可。
kblack 的 std 是暴力讨论各种情况的，写起来可能有些繁琐。
可能是存在这个性质的，而且不仅限于有素因子 $\ge 1000$ 的时候才成立。验题人好像就是基于这个性质写了暴力。