C++でN番目の項を求める方法（行列累乗の活用例）

この問題では、整数Nと、N番目の項をそれ以前の項の関数として定義する漸化式が与えられます。求めるのは、N番目の項を計算するプログラムです。ここでは、再帰による単純な解法と、行列累乗（Matrix Exponentiation）を使った効率的な解法の2通りを解説します。

今回扱う漸化式は以下のとおりです。

T(n) = 2 * T(n-1) + 3 * T(n-2)
初期値：T(0) = 1、T(1) = 1

入力例と出力例

入力：

N = 4

出力：

41

計算の流れ：

T(4) = 2 * T(3) + 3 * T(2)
T(4) = 2 * (2 * T(2) + 3 * T(1)) + 3 * (2 * T(1) + 3 * T(0))
T(4) = 2 * (2 * (2 * T(1) + 3 * T(0)) + 3 * 1) + 3 * (2 * 1 + 3 * 1)
T(4) = 2 * (2 * (2 + 3) + 3) + 3 * 5
T(4) = 2 * (10 + 3) + 15
T(4) = 2 * 13 + 15 = 26 + 15 = 41

解法1：再帰による単純な解法

最もシンプルな方法は、再帰または反復処理を利用することです。N番目の項を前の項の再帰呼び出しとして定義し、初期値を基準に結果を求めます。この方法は理解しやすい反面、再帰呼び出しが重なり、計算量が指数関数的に増大するという弱点があります。

サンプルコード

#include <iostream>
using namespace std;

long calcNthTerm(long n) {
    if(n == 0 || n == 1)
        return 1;
    return ( ( 2 * (calcNthTerm(n-1)) ) + ( 3 * (calcNthTerm(n-2)) ) );
}

int main() {
    long n = 5;
    cout << n << "番目の項の値は " << calcNthTerm(n);
    return 0;
}

出力：

5番目の項の値は 121

解法2：行列累乗を使った効率的な解法

より効率的に解くには、行列累乗の考え方を利用します。この手法では、漸化式を表す「変換行列」を構成し、その累乗を計算することでN番目の項を求めます。

変換行列のサイズは、依存する項の数（この場合は2）によって決まります。初期値は T(0) = 1、T(1) = 1 です。

変換行列は k×k の正方行列となり、k×1 の初期行列と掛け合わせることで次の項が得られます。今回の設定は以下のとおりです。

初期行列（IM）：

$$\begin{bmatrix}T(1) \\ T(0) \end{bmatrix} = \begin{bmatrix}1 \\ 1 \end{bmatrix}$$

変換行列（TM）：

$$\begin{bmatrix}2 & 3 \\ 1 & 0 \end{bmatrix}$$

このとき、N番目の項は次の式で求められます。

$$T_n = \begin{bmatrix}2 & 3 \\ 1 & 0 \end{bmatrix}^{n-1} \times \begin{bmatrix}1 \\ 1 \end{bmatrix}$$

行列の累乗は、指数を半分にしながら繰り返し二乗（バイナリ法）で計算することで、O(log N) の計算量に抑えられます。これにより、Nが非常に大きい場合でも高速に答えを求められます。

サンプルコード

#include <iostream>
using namespace std;
#define MOD 1000000009

long calcNthTerm(long n) {
    if (n <= 1)
        return 1;
    n--;
    long resultantMat[2][2] = { 1, 0, 0, 1 };
    long transMat[2][2] = { 2, 3, 1, 0 };
    while (n) {
        long tempMat[2][2];
        if (n & 1) {
            tempMat[0][0] = (resultantMat[0][0] * transMat[0][0] +
            resultantMat[0][1] * transMat[1][0]) % MOD;
            tempMat[0][1] = (resultantMat[0][0] * transMat[0][1] +
            resultantMat[0][1] * transMat[1][1]) % MOD;
            tempMat[1][0] = (resultantMat[1][0] * transMat[0][0] +
            resultantMat[1][1] * transMat[1][0]) % MOD;
            tempMat[1][1] = (resultantMat[1][0] * transMat[0][1] +
            resultantMat[1][1] * transMat[1][1]) % MOD;
            resultantMat[0][0] = tempMat[0][0];
            resultantMat[0][1] = tempMat[0][1];
            resultantMat[1][0] = tempMat[1][0];
            resultantMat[1][1] = tempMat[1][1];
        }
        n = n / 2;
        tempMat[0][0] = (transMat[0][0] * transMat[0][0] +
        transMat[0][1] * transMat[1][0]) % MOD;
        tempMat[0][1] = (transMat[0][0] * transMat[0][1] +
        transMat[0][1] * transMat[1][1]) % MOD;
        tempMat[1][0] = (transMat[1][0] * transMat[0][0] +
        transMat[1][1] * transMat[1][0]) % MOD;
        tempMat[1][1] = (transMat[1][0] * transMat[0][1] +
        transMat[1][1] * transMat[1][1]) % MOD;
        transMat[0][0] = tempMat[0][0];
        transMat[0][1] = tempMat[0][1];
        transMat[1][0] = tempMat[1][0];
        transMat[1][1] = tempMat[1][1];
    }
    return (resultantMat[0][0] * 1 + resultantMat[0][1] * 1) % MOD;
}

int main() {
    long n = 5;
    cout << n << "番目の項の値（行列累乗による計算）は " << calcNthTerm(n);
    return 0;
}

出力：

5番目の項の値（行列累乗による計算）は 121

まとめ

単純な再帰による解法は実装が容易ですが、計算量がO(2^N)に近づき、Nが大きくなると実用性が失われます。一方、行列累乗を用いた解法は、繰り返し二乗の仕組みによりO(log N)でN番目の項を求められるため、競技プログラミングなどで大きなNを扱う際に非常に有効です。漸化式の形が線形であれば、同様の手法をフィボナッチ数列など他の数列にも応用できます。