AtCoder Beginner Contest 129 题解

AC Codes

A – Airplane

B – Balance

C – Typical Stairs

D – Lamp

给定一个 $H\times W$ 的带障碍物的网格图，询问在某个点放一盏灯最多能够照亮几个单元格。灯只能照亮上下左右四个方向，并且光线遇到障碍物后就会停止。

$H, W \leq 2000$ 。

直接开四个矩阵分别存储 $(i,j)$ 这个点向上下左右四个方向最远能走几步。

E – Sum Equals Xor

给定 $L$ 求满足 $a+b\leq L$ 并且 $a\oplus b = a+b$ 的自然数 $(A,B)$ 对数。

$L\leq 2^{100001}$ 。

不懂数位 dp，因此直接找规律，不难发现规律是 $a [n] = 3\times a [\lfloor\frac {n}{2}\rfloor] + (n \bmod 2)\times2^{popcount (n-1)}$ ，用记忆化搜索即可解决本题。

F – Takahashi’s Basics in Education and Learning

等差数列 $s$ 满足 $s_i=A+Bi$ ，将前 $L$ 项 $s_i$ 首尾相连构成大数模 $M$ 的值。比如样例 $3,7,11,15,19$ 就会拼接成 $37111519$ 。

$1\leq A,B,L\leq 10^{18},M\leq 10^9$ 并且保证 $s_i\leq 10^{18}$ 。

做法不是很难，但是边界处理很繁琐，~~代码打了一整天~~。

先观察样例 $A=3,B=4,L=5$ ：

\begin{matrix} 3 & \times 10^7\\ 3+4 & \times 10^6\\ 3+4+4 & \times 10^4\\ 3+4+4+4 & \times 10^2\\ 3+4+4+4+4 & \times 10^0\\ \end{matrix}

稍微变形一下：

\begin{aligned} &3 \times (10^7+10^6+10^4+10^2+10^0)\\ &4 \times (10^6+10^4+10^2+10^0)\\ &4 \times (10^4+10^2+10^0)\\ &4 \times (10^2+10^0)\\ &4 \times 10^0\\ \end{aligned}

再来个更明显的样例 $A = 1,B = 25, L = 6 (1,26,51,76,101,126)$ ：

\begin{matrix} 1 & \times 10^{12}\\ 1+25 & \times 10^{10}\\ 1+25+25 & \times 10^8\\ 1+25+25+25 & \times 10^6\\ 1+25+25+25+25 & \times 10^3\\ 1+25+25+25+25+25 & \times 10^0\\ \end{matrix}

稍微变形一下：

\begin{aligned} &1 \times (10^{12}+10^{10}+10^8+10^6+10^3+10^0)\\ &25 \times (10^{10}+10^8+10^6+10^3+10^0)\\ &25 \times (10^8+10^6+10^3+10^0)\\ &25 \times (10^6+10^3+10^0)\\ &25 \times (10^3+10^0)\\ &25 \times 10^0 \end{aligned}

可以注意到一个重要事实： $10^d$ 可以看作一个分段的等差数列，而且根据数据范围公差最大不超过 $18$ 。然后，以上方的样例 $A = 1,B = 25, L = 6$ 为例，首先出现了一个等差三角形：

\begin{aligned} 10^6+10^3+10^0\\ 10^3+10^0\\ 10^0 \end{aligned}

公差发生变化后，又出现了一个新的等差三角形：

\begin{aligned} 10^{12}+10^{10}+10^8\\ 10^{10}+10^8\\ 10^8\\ \end{aligned}

对于某个等差三角形（假设有 $k$ 层）

\begin{aligned} 10^0\\ 10^0+10^q\\ 10^0+10^q+10^{2q}\\ \cdots\\ 10^0+10^q+\cdots+10^{(k-1)q} \end{aligned}

我们需要求解的是这个三角形最后一行的和，以及这个三角形整体的和。最后一行的求和显然就是等差数列求和，而整个三角形的求和则可以写成：

\begin{aligned} \sum_{i=0}^{k-1}(k-i)\times 10^{iq} \end{aligned}

这种等差 x 等比的合成数列求和有一个经典方法：错位相减（相信高中数学里一定学过）。

\begin{matrix} k\times 10^0 & (k-1)\times 10^q & (k-2)\times 10^{2q} & \cdots & 10^{kq} & & S\\ &k\times 10^q & (k-1)\times 10^{2q} & \cdots & 2\times10^{kq} & 10^{(k+1)q} & 10^qS \end{matrix}

上下相减后得到：

\begin{aligned} 10^qS-S&=10^q+10^{2q}+\cdots + 10^{kq}+10^{(k+1)q}-k\\ S &= \frac{\frac{10(1-q^k)}{1-q}-k}{10^q – 1}\\ \end{aligned}

但是！本题中的模数可能为合数，因此直接这么做是不行的（逆元不存在）。观察到这个三角形的递推性质，不妨令数列 $a_i=10^0+10^q+\cdots+10^{(i-1) q}$ ，于是有以下递推关系 $a_{i+1}=10^qa_i+1$ ，差分一下得到：

\begin{aligned} a_{i+2}-a_{i+1}=10^qa_{i+1}-10^qa_i\Leftrightarrow a_{i+2}=(10^q+1)a_{i+1}-10^qa_i \end{aligned}

注意到这是一个常系数齐次线性递推数列，因此可以求出该数列的生成函数 $f$ ，答案就是 $[x^{k-1}]\frac {f}{1-x}$ 。