AtCoder Beginner Contest 179 题解

AC Codes

A – Plural Form

B – Go to Jail

C – A x B + C

直接暴力枚举就能 $O (N\log N)$ 解决了。但是本题还可以优化为 $O (\sqrt {N})$ 。我们可以改写问题为：有几对 $(A,B)$ 满足 $AB\leq N$ 。

那么一共三类情况：

显然情况 1 可以 $O (\sqrt {N})$ 枚举，情况 2 和 3 是对偶情况，都可以用数论分块或者简单的数学分析（$A<B\leq \lfloor\frac {N}{A}\rfloor$）解决。

D – Leaping Tak

有 $N$ 个单元格排成一列，初始位于第一个单元格。现在有 $K$ 个不相交区间 $[L_i,R_i]$ ，当你位于第 $d$ 个单元格时，你可以选择某个区间 $i$ ，并且跳跃到 $[d+L_i,d+R_i]$ 中任意一个单元格。询问恰好跳到第 $N$ 个单元格的方案数。

$N\leq 2\times 10^5,K\leq \min(10,N)$ 。

题目可以转化为：给定一个数组 $\{c_1,c_2,\ldots,c_k\}$ 我能够从 $d$ 跳跃到 $d+c_1,d+c_2,\ldots,d+c_k$ ，询问从 $1$ 跳到 $N$ 的方案数。

这很显然可以用形式幂级数来搞，构造多项式 $f=x^1,g=x^{c_1}+x^{c_2}+\cdots+x^{c_k}$ 答案就是 $[x^N] f+fg+fg^2+\cdots = [x^N]\sum_{i=0}^{\infty} fg^i$ 。

通过等比数列求和的方法，很显然可以转化为 $[x^N]\frac {f}{1-g}$ 。然后多项式求逆 + 多项式乘法 $O (N\log N)$ 求解。

E – Sequence Sum

定义 $f (x,m)=x^2\pmod {m}$ ，给定 $A_1=X$ ，求 $\sum_{i=1}^Nf (A_i,M)$ 。

$N\leq 10^{10},0\leq X<M\leq 10^5$ 。

由于 $M$ 不大，所以我们可以找到这个数列的循环节（循环节长度一定小于模数），找到循环节后就可以在 $O (M)$ 的时间复杂度下计算了。需要注意的是这个循环节可能是混循环。

F – Simplified Reversi

懒得翻译了，看一下题面样例的图估计就懂了。

关键是注意到：如果我们翻转了第 $i$ 列，那么第 $j (j>i)$ 列上的棋子都无法被横向的操作影响，因此我们需要维护的就是当前翻转过的最左侧那一列和最上方那一行，这是棋盘左上方的一个长方形区域。

这很显然只需要一个区间覆盖操作就可以完成，拿线段树维护即可。（其实可以注意到，我们需要维护的区间是一个逐渐缩短的前缀，所以根本不需要数据结构就能维护）