Sweetlemon 的博客

Sweetlemon 的博客

AGC 047 总结

posted on 2020-08-11 10:42:12 | under 总结 |

退役前打的第一场也是最后一场 AGC,感觉还是比较有趣的,思维含量挺足。

赛时只做了 A,B,C,而且 C 还被卡精度(哭)。赛后做了好玩的 E。

A Integer Product

给 $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

定义操作 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

令 $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 函数,这是一个 C++ 11 的“计算最接近整数值”函数,看上去挺有用。

E Product Simulation

(相当于)提交答案题,而且是造计算机题。交一段程序,计算两个自然数的乘积。

这个计算机的内存有 $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$。