Codeforces 379D New Year Letter：構造含指定 AC 子串數的費波納契字串

題目大意

給定 k, x, n, m。構造長度為 n 的 s1 和長度為 m 的 s2（大寫字母），定義 sₙ = sₙ₋₂ + sₙ₋₁（字串拼接）。要求 sₖ 中子串 "AC" 出現恰好 x 次。k ≤ 50, x ≤ 10⁹, n,m ≤ 100。

關鍵觀察

• sₖ 由 s1, s2 按費波納係數拼接而成：`sₖ = Fₖ₋₂*s1 + Fₖ₋₁*s2`（字串重複拼接意義）
• "AC" 數量 = 內部 "AC" + 跨邊界 "AC"（前字串末尾 'A' + 後字串開頭 'C'）
• 只需考慮 s1, s2 的**首尾字符**與**內部 AC 數**

狀態枚舉

枚舉 s1, s2 的首尾字符（只需考慮 'A','B','C' 三類，其他字母等價於 'B'）。共 3⁴=81 種組合。再枚舉 s1 內部 AC 數 i (0~max1)，s2 內部 AC 數 j (0~max2)。max 由長度與首尾決定。

費波納契加速計算

預計算 `fib[t] = fib[t-1] + fib[t-2]` 表示 sₖ 中 s1/s2 的重複次數。總 AC 數 = `dp[k] + i*fib1[k] + j*fib2[k]`。`dp[k]` 為跨邊界貢獻，可遞推預計算。

構造具體字串

找到合法 (首尾, i, j) 後，構造 s1：按首尾與 i 填充 'A','C'，其餘填 'B'。同理構造 s2。優先輸出任意合法解。

複雜度

枚舉 81 × 50 × 50 ≈ 20萬，極快。k=50 時費波納契數極大，需 `long long` 並剪枝超限值。