SP11383 FAST2 - Fast Sum of two to an exponent 题解

喵仔牛奶 · 2022-12-26 11:23:13 · 题解

显然等比数列求和。

问题：求 \sum_{i=0}^{n}p^i。

解：

令 S_0=\sum_{i=0}^{n}p^i,S_1=\sum_{i=1}^{n+1}p^i，

显然 S_1=pS_0。

S_1-S_0=(p-1)S_0=\sum_{i=1}^{n+1}p^i-\sum_{i=0}^{n}p^i=p^{n+1}-p^{0}

(p-1)S_{0}=p^{n+1}-1

S_0=\dfrac{p^{n+1}-1}{p-1}

本题 p=2，所以 S_{0}=\dfrac{2^{n+1}-1}{2-1}=2^{n+1}-1。

T = int(input())
for i in range(T):
    n = int(input())
    print((2 ** (n + 1) - 1) % 1298074214633706835075030044377087)