NYOJ 1075 紅色病毒：遞推關系與矩陣快速冪求 DNA 序列數

狀態定義與遞推

DNA 由 A,C,G,T 組成。要求 A 和 C 均成對出現（即個數為偶數）。定義 4 狀態：

• 0: A偶, C偶
• 1: A偶, C奇
• 2: A奇, C偶
• 3: A奇, C奇

轉移矩陣 M[4][4]：

| 2 1 1 0 |
| 1 2 0 1 |
| 1 0 2 1 |
| 0 1 1 2 |

含義：添加 G/T 不改變奇偶（係數 2）；添加 A 翻轉 A 奇偶；添加 C 翻轉 C 奇偶。初始狀態為 0（空串 A=0偶, C=0偶）。答案為 (M^n)[0][0] mod 10007。

矩陣快速冪模板

struct Matrix { int m[4][4]; };
Matrix mul(Matrix a, Matrix b) {
    Matrix r;
    for i,j,k: r.m[i][j] = (r.m[i][j] + a.m[i][k]*b.m[k][j]) % MOD;
    return r;
}
Matrix pow(Matrix a, long long n) {
    Matrix r = identity();
    while (n) { if (n&1) r = mul(r, a); a = mul(a, a); n >>= 1; }
    return r;
}

主程序讀入多組 n，輸出 pow(M, n).m[0][0]。n 可達 1e9，log₂n ≈ 30 步，極快。