【題解】ZeroJudge e827: 2.道路鋪設 (Roads)

【題目敘述】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)

分享本文 Share with friends