AGC 047 总结

退役前打的第一场也是最后一场 AGC，感觉还是比较有趣的，思维含量挺足。 赛时只做了 A,B,C，而且 C 还被卡精度（哭）。赛后做了好玩的 E。 ### [A Integer Product](https://atcoder.jp/contests/agc047/tasks/agc047_a) 给 $n$ 个不超过 $10^4$、小数点后不超过 $9$ 位的正有理数 $a_1,a_2,\cdots,a_n$，计算有多少个二元组 $i,j\ (i<j)$ 满足 $a_ia_j$ 是整数。 看到相乘为整数，首先想到了化为分数。可是小数点后不超过 $9$ 位，我难道要处理 $10^9$ 以下的质数吗？ 走动休息的时候突然想到了重要的点，这些都是有限小数，分母的质因子只有 $2$ 和 $5$ 啊，那每个数记录一下 $2$ 和 $5$ 的次数（分子减去分母），这两个次数的范围都不是很大，接下来把数按照次数分组，枚举两个组讨论一下不就好了嘛。 另外，同一个组的数，如果都是整数，是可以两两相乘得到整数的，要稍微注意一下。 ### [B First Second](https://atcoder.jp/contests/agc047/tasks/agc047_b) 定义操作 A 为，对一个字符串，每次可以删除开头的**第**一个或**第**二个字符，可以进行任意次删除。给定 $n\ (n\le 200000)$ 个互不相同的字符串，总长不超过 $10^6$，计算有多少对字符串 $(S_i,S_j)\ (S_i\neq S_j)$，使得 $S_i$ 可以通过操作 A 变为 $S_j$。 总长是 $10^6$，那么大概没有很离谱、很毒瘤的算法。首先，这个操作肯定有玄机。经过讨论我们发现，一定存在一种等效的操作方案，方案中一旦开始删第二个字符（这意味着我们想要保留当前的第一个字符），就不再删第一个字符了。 因此操作 A 可以得到一个字符串的某个字符拼接上这个字符串的一个（可空）后缀，后缀一定在这个字符的后面。 于是操作 A 可以用哈希来快速模拟，我们也就可以用哈希加 map（或者哈希加哈希表）来完成这道题了。注意字符串要按长度加入，还要注意避免重复计数。 花希酱赛高！ ### [C Product Modulo](https://atcoder.jp/contests/agc047/tasks/agc047_c) 令 $p=200003$（质数），给定 $n\ (n\le 200000)$ 个非负整数，计算 $\sum_{1\le i<j\le n}(a_ia_j\bmod p)$，即乘法的时候要取模，求和不取模。 这题看上去很怪异，如果两个运算都取模或都不取模，我们就能很快解决。于是赛时我就花了很长时间，想要用 $\sum a_ia_j$ 和 $\sum \left\lfloor\cfrac{a_ia_j}{p}\right\rfloor$ 来计算，结果后者根本没有任何思路。 后面想到，$a_ia_j\bmod p$ 只有 $p$ 种结果，如果能找出每种结果的出现次数，也能够计算出答案。但是一开始陷于普通的模意义运算之中，仍然没有思路。 最后一点时间，突然想到了 WC 刚出现的原根，突然就想到了正解；$uv=w$ 不就等价于 $\log u+\log v=\log w$ 嘛，后者可以用 FFT 卷积完成。于是先找原根，很快找到了一个原根 $5$；再快速写完预处理指标，最后粘一个 NTT 模板——WA 了！ 原来我对答案的估计是不正确的，如果有 $10^5$ 个数是 $2$，$10^5$ 个数是 $3$，那么乘起来为 $6$ 的结果岂不是有 $10^{10}>998244353$ 个？所以还得用普通 FFT。 快速改模板，结果又 WA 了！赛后拼命调 EPS，结果要 FFT 的结果加上 $0.1$ 再下取整才能过，加 $0.5$ 下取整、加 $0.00001$ 下取整都不能过。 看题解，套的居然是三次变两次模板（这是自乘，其实没必要三次变两次），结果居然精度也没问题？再一看，用了 [`llround` 函数](https://zh.cppreference.com/w/cpp/numeric/math/round)，这是一个 C++ 11 的“计算最接近整数值”函数，看上去挺有用。 ### [E Product Simulation](https://atcoder.jp/contests/agc047/tasks/agc047_e) （相当于）提交答案题，而且是造计算机题。交一段程序，计算两个自然数的乘积。 这个计算机的内存有 $200000$ 个单元 $a_0,a_1,\cdots,a_{199999}$，每个单元能存放一个不大于 $10^{19}$ 的自然数。 这个计算机的指令只有两种： - `+ i j k`，其中 $i,j,k$ 是合法的内存索引，也就是 $i,j,k$ 是 $[0,200000)$ 之间的整数（而且是“编译时”确定的常数）。这条指令的效果是 $a_k\leftarrow a_i+a_j$。 - `< i j k`，$i,j,k$ 含义同上，使得 $a_k\leftarrow [a_i<a_j]$（也就是将一个零或一的值赋给 $a_k$）。 初始时 $a_0,a_1$ 分别存放了一个 $[0,10^9]$ 之间的自然数（记为 $A,B$），你希望在执行不超过 $200000$ 条指令后，使 $a_2$ 处存放 $A\times B$。 这道题十分有趣，但也有些棘手，因为没有分支结构，只能顺序执行。 当天睡前我一直在想，如何实现乘法呢？想了一会儿没有思路，我就想着，我先实现一些基础运算吧，于是就实现了与、或、非、异或这些，后来想到，如果能把这两个数化成二进制，再用位运算进行乘法（就是卷积），最后化成十进制，不就完成了吗？ 然后就想了，如何构造 $1$，如何构造 $2$ 的幂，接着用倍增作二进制拆分（用到的手段有点类似题解的条件表达式），卷积二进制乘法，最后倍增化为十进制。咦，怎么感觉不需要 $200000$ 个内存单元，也不需要 $200000$ 条指令呢？是不是我想假了？ 后来实现了一下，实现时边写文档边写代码，最后用六千多条指令解决了问题。翻一翻题解，好像我这个指令数还是比较优的嘛。 接着突然想到化为十进制的过程可以用秦九韶算法优化，指令数降到了四千二百多条。 后来又想到，这个题不仅可以做乘法，化为二进制后还可以减法（可能取绝对值），还可以排序（$\mathrm{O}(n^2)$ 的冒泡排序和 $\mathrm{O}(n\log n)$ 的堆排序似乎都可以实现）。~~毒瘤题预备~~ 附上我写代码的同时写出来的文档。 #### 寄存器设计 $0, 1, 2$：输入输出保留寄存器 $3$：零寄存器 $N-0, N-1, ... N-60$：$N-k$ 存储 $2^k$ $4\sim 10$：位运算寄存器 $11\sim 20$：函数寄存器 $30\sim 60$：$a$ 的二进制表示寄存器 $70\sim 100$：$b$ 的二进制表示寄存器 $110\sim 170$：$a\cdot b$ 的二进制表示寄存器 #### 基本函数 ##### make_pw 制作 $2^k$ 系列函数。指令数 $62$。 ##### lmv 将 $x$ 位置的数左移 $k$ 位。指令数 $k$。 ##### land 参数 $x,y,z$。令 $z=x\land y$。使用位运算寄存器 $4$。指令数 $2$。 ##### to_bin 参数 $x,l,k$，将 $x$ 位置的数进行二进制分解，最高位为 $2^k$，放到 $[l,l+k]$ 位置，低位在前。使用函数寄存器 $11,12,13$。指令数 $4k+\frac{k(k+1)}{2}+6$。 ##### to_dec 参数 $x,l,k$，将 $[l,l+k]$ 位置的二进制数（不必规范）恢复为十进制，返回到 $x$ 位置。使用函数寄存器 $15$。指令数 $2k$。 ##### mult 参数 $l_1,l_2,l_3,k$，将 $[l_1,l_1+k]$ 和 $[l_2,l_2+k]$ 两个范围的数相乘，存储在 $[l_3,l_3+2k]$ 范围内，结果不一定是规范二进制数。使用函数寄存器 $14$。指令数 $3(k+1)^2$。 ##### sub 参数 $x,y,z,k$，$k$ 表示 $\max(x,y)<2^{k+1}$。令 $z=\max(x-y,0)$。使用函数寄存器 $16,17,18$。指令数 $4k+\frac{k(k+1)}{2}+7$。