题解 P8629 [蓝桥杯 2015 国 C] 机器人繁殖 题解

· · 题解

题目传送门

看到几个大佬的题解，深感数学不行。本蒟蒻就来发一个小学生都能看懂的找规律题解。

思路

我们假设开始时有 t 个机器人。我们记 f(x) 为 x 年后的机器人个数，然后我们开始尝试前几项：

\begin{aligned} f(1) &= t+(2t-1) &= 3t-1 \\ f(2) &= 3t-1+(2(2t-1)-1) &= 7t-4 \\ f(3) &= 7t-4+(2(4t-3)-1) &= 15t-11 \\ f(4) &= 15t-11+(2(8t-7)-1) &= 31t-26 \\ f(5) &= 31t-26+(2(16t-15)-1) &= 63t-57 \\ \cdots \end{aligned}

我们先看结果含 t 的一次项：

3t\quad7t\quad15t\quad31t\quad63t\cdots

取他们系数的差可以发现，差的数列为：

4\quad8\quad16\quad32\cdots

又因为 3=1+2，我们记 A(x) 为一次项系数，x 为过去的时间，可以得到以下关系：

A(x)=1+2+4+\cdots+2^x=2^{x+1}-1

接下来看常数项：

1\quad4\quad11\quad26\quad57\cdots

取差：

3\quad7\quad15\quad31\cdots

有没有觉得很眼熟，这就是一次项系数的规律。

所以我们记 B(x) 为常数项，x 为所过的时间，可以得到以下关系：

B(x)=\sum^{x}_{i=1}A(i-1)

当然 B(0) 是特例，B(0)=0。

现在我们来计算一下 B(x) 的通项公式：

\begin{aligned} B(x) &= \sum^{x}_{i=1}A(i-1)\\ &= A(0)+A(1)+\cdots+A(x-1)\\ &= (2^1-1)+(2^2-1)+\cdots+(2^{x}-1)\\ &= (2^{x+1}-2)-x\\ \end{aligned}

所以基本上就大功告成了！

所以 n 年后的机器总数为：

\begin{aligned} s &= A(n)t+B(n)\\ &= (2^{n+1}-1)t-[(2^n-2)-n]\\ &= 2^{n+1}t-t+n-2^{n+1}+2\\ &= (2^{n+1}-1)(t-1)+t+1\\ \end{aligned}

把它化简表示为 t 的函数形式，易得

t=\frac{s-n-1}{2^{n+1}-1}+1

最后看到样例二的那一大串数字 2218388550399401452619230609499，我们肯定要用高精度。作为一个蒟蒻，高精度肯定用 Python 啦！

AC 代码

#Python代码
from math import pow
n,s = input().split(" ")
n,s = int(n),int(s)
print(str(int((s-n-1)/(int(pow(2,n+1))-1)+1)))

AC 记录