洛谷P2558 [AHOI2002] 网络传输 题解
题意：
在计算机网络中所有数据都是以二进制形式来传输的。但是在进行较大数据的传输时，直接使用该数的二进制形式加以传输则往往传输的位数过多。譬如要传输 $1024$ 就需要 $11$ 位二进制数。于是小可可提出了一种数据优化传输的设想，并打算对这一设想进行试验。
该设想是：正整数的所有方幂以及任意多个互不相等的 $k$ 的方幂之和排成一个递增数列 $\{a(k)n\}$，例如当 $k=3$ 时，$\{a(k)n\}$ 的前 $7$ 项为 $1(=3^0)$ 、 $3(=3^1)$ 、 $4(=3^0+3^1)$ 、 $9(=3^2)$ 、 $10(=3^0+3^2)$ 、 $12(=3^1+3^2)$ 、 $13(=3^0+3^1+3^2)$。
如果数 $d$ 是数列 $\{a(k)n\}$ 中的第 $p$ 项，则可以通过传送 $k$ 和 $p$ 这两个数来表示数 $d$。由于 $k$ 和 $p$ 这两个相对很小的数就可以表达出很大的数，因而理论上可以减少网络传输的位数。
小可可现在请你编写程序把接收到的数 $k$ 和 $p$ 所代表的数 $d$ 计算出来。
输入格式：
文件中以一行的形式存放了两个正整数 $k$ 和 $p$，$1<k \le 1024$，$1 \le p \le 1024$。
输出格式：
以一行的形式输出问题的解（解的位数不超过 $50$ 位）。
还以为是什么格雷码，结果是个自创的编码方式。
题目讲的也不清楚，只能仔细观察它的构成，容易发现（以下 $i\ge 1$ ）
- 对于 $i~(2^k < i < 2^{k + 1})$ 有 $f_i = f_{i\bmod k}+f_k$ 。
- 对于 $i = 2^k$ 有 $f_i = a^k$ 。
注意本题需要高精度，当然我肯定不高兴打高精的，直接上 python 。
时间复杂度 $\mathcal{O}(n)$
代码：
a, b = map(int, input().split())
f = []; base = 1; now = 0; num = 0;
while True:
f.append(base)
num += 1
now = num
base *= a
for i in range(0, now - 1):
f.append(f[now - 1] + f[i])
num += 1
if num >= b:
print(f[b - 1])
break参考文献：
[1] https://www.luogu.com.cn/article/o3zw1bt4
题外话：
原来 python 没有自增运算符啊，白学了。
