洛谷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 没有自增运算符啊，白学了。
