【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e827
【解題想法】快速冪
- L = 2：兩個單位長度間有一次選擇的機會，「分成兩段」或「連在一起」。答案是2^1 = 2。
- L = 3：三個單位長度間有兩次選擇的機會，「分成兩段」或「連在一起」。答案是2^2 = 4。
- L = 4：四個單位長度間有三次選擇的機會，「分成兩段」或「連在一起」。答案是2^3 = 8。
- 因此，答案是 2 ^ (L-1)
- L的值很大， 1<=L<=10^9，採用快速冪來計算。
- 10^9 < 2 ^ 31
#include <iostream>
using namespace std;
int t, l;
long long mul, ans, mod = 1e9+7;
int main() {
cin >> t;
while (t--){
cin >> l;
l--; //答案是 2^(L-1)
mul = 2;
ans = 1;
for (int i = 0; i < 32; i++){
if (l & (1<<i)){
ans *= mul;
ans %= mod;
}
mul *= mul;
mul %= mod;
}
cout << ans << "\n";
}
}
Python code (credit: Amy Chou)
- mod = 1000000007 (不能寫成 1e9+7，會變成浮點數型態)
import sys
mod = 1000000007
for line in sys.stdin:
T = int(line)
for _ in range(T):
L = int(sys.stdin.readline())
L -= 1
mul = 2
ans = 1
for i in range(32):
if (L & (1 << i)):
ans *= mul
ans %= mod
mul *= mul
mul %= mod
print(ans)