BNUOJ 34976 數細菌：矩陣快速冪求遞推第 n 項

BNUOJ 34976 - 細菌分裂遞推：矩陣快速冪求 log10(答案)

細菌分裂規律：第 1 天 1 個新分裂，第 2 天仍 1 個，第 3 天 3 個，第 4 天 3 個，第 5 天 9 個... 即奇數天數列：1, 3, 9, 27...（等比數列），偶數天與前一天相同。已知第 1 天 a 個、第 2 天 b 個，求第 n 天總數，輸出 log10(總數)。a,b,n ≤ 1e18。

遞推關係

設 f[n] 為第 n 天新分裂數。
f[1]=1, f[2]=1, f[3]=3, f[4]=3, f[5]=9...
發現：f[2k-1] = 3^{k-1}, f[2k] = 3^{k-1}。
總數 S[n] = Σ_{i=1}^n f[i]。
若 n=2m：S[2m] = 2 × Σ_{i=0}^{m-1} 3^i = 2 × (3^m - 1)/2 = 3^m - 1
若 n=2m+1：S[2m+1] = S[2m] + 3^m = 2×3^m - 1

通項公式

n 奇數（n=2m+1）：總數 = 2×3^m - 1
n 偶數（n=2m）：總數 = 3^m - 1

但題目給定 a,b 為第 1、2 天總數，非標準初始值。實際為線性遞推：
S[n] = S[n-1] + f[n]，f[n] = 3×f[n-2]（n≥3）
即 S[n] = S[n-1] + 3(S[n-2] - S[n-3])，三階線性遞推。

矩陣快速冪

構造 3×3 矩陣：

[ S[n]   ]   [ 1  0  3 ]   [ S[n-1] ]
[ S[n-1] ] = [ 1  0  0 ] × [ S[n-2] ]
[ S[n-2] ]   [ 0  1  0 ]   [ S[n-3] ]

初始向量 [b, a, 0]^T（S[0]=0）。n≤1e18 需 O(log n) 矩陣冪。結果取 log10 輸出。

大數處理

結果極大（3^{5e17}），不能直接存儲。矩陣乘法中每項取 log10 運算：
log10(x+y) ≈ log10(x) + log10(1 + 10^{log10(y)-log10(x)})（x≥y）
或用高精度浮點（long double 80位尾數足夠 log10(3^5e17) ≈ 2.38e17 的指數部分）。

簡化：直接用公式

觀察遞推，實際 S[n] 為 α·3^{⌊n/2⌋} + β 形式。由 a=S[1], b=S[2] 解出係數，直接計算 log10(S[n])。但矩陣快速冪更通用、不易出錯。