第３問「ヒストリー和」問題 解答

「ヒストリー和」問題の解法です。
問題文はこちら。
他の問題の解法は、第１問、第２問、第４問、第５問。

漸化式にしたがって F_k(n) の項の値を求める問題です。
求めるべき答えは、(k, n) = (10, 10¹⁰) と (10⁴, 10⁶) に対する値の和です。
やけに奇妙な組み合わせだな、と思われたかもしれません。
実は本問は、2 つの場合でそれぞれ異なる解法が必要です。

(k, n) = (10, 10¹⁰) のとき

F_k(n) の値は、直前の 10 項の値によって決まります。
行列で書くとこういうことです。

行列をべき乗する典型的な問題に帰着できます。
計算量は O(k³ log n) となります。

(k, n) = (10⁴, 10⁶) のとき

上記のべき乗の方法でこちらの組を解こうとすると、k が大きすぎてうまくいきません。
まったく別のアプローチが必要になります。

F_k(n) だけでなく、直近 k 項の和として G_k(n) を新たに定義することがポイントです。

G_k(n) を使うと、例えば k = 5 の場合、F_k(n) の漸化式は次のように表せます。

一般的に書くとこういうことです。

G_k(n) の値を求めるには、まず長さ k の配列を用意します。
これをリングバッファとして用いて、直近 k 個の値を保持しておきます。
さらにこの和を別に変数として持っておいて、都度更新するようにすれば、n 回程度の計算でG_k(n) の値が求められます。

計算量は O(n) です。

以上の 2 通りの解法を切り替えれば、最終的な答えが出せます。コード例は以下になります。

D = 100000000

def pow_mod(x, m):
    if m == 1: return x
    if m % 2 == 0:
        p = pow_mod(x, m / 2)
        return mul(p, p)
    else:
        p = pow_mod(x, m - 1)
        return mul(x, p)

def mul(x, y):
    z = [[0 for i in range(len(y[0]))] for j in range(len(x))]
    for i in range(len(x)):
        for j in range(len(y[0])):
            for k in range(len(x[0])):
                z[i][j] = (z[i][j] + x[i][k] * y[k][j]) % D
    return z

def f_matrix(n, k):
    m = [[] for i in range(k)]
    for i in range(k-1):
        for j in range(k):
            m[i].append(1 if i+1==j else 0)
    for j in range(k):
        m[k-1].append(j+1)
    p = pow_mod(m, n+1)
    return p[k-1][0]

def f_buffer(n, k):
    h, f, g = [0]*k, k, 1
    p = 0
    h[0], h[1] = 1, k
    for i in range(2, n+1):
        f_new = f*(k+1) - g
        g_new = g - p + f
        p = h[i%k]
        h[i%k] = f_new
        f, g = f_new % D, g_new % D
    return f

print (f_matrix(10000000000, 10) + f_buffer(1000000, 10000)) % D