AND と XOR は、それぞれ「掛け算」と「足し算」に対応するので、行列累乗が使える！

問題へのリンク

問題概要

$K$ 個の整数の組 $A_{1}, \dots, A_{K}$ と $C_{1}, \dots, C_{K}$ が与えられる。

数列 $a_{1}, a_{2}, \dots$ は次の漸化式で定義される。

$a_{i} = A_{i}$ ( $i = 1, 2, \dots, K$ )
$a_{i+K} = (C_{1}$ AND $a_{i+K-1})$ XOR $(C_{2}$ AND $a_{i+K-2})$ XOR ... XOR $(C_{K}$ AND $a_{i})$ ( $i \ge 1$ )

$a_{M}$ の値を求めよ。

制約

$1 \le K \le 100$
$1 \le M \le 10^{9}$

考えたこと

AND は掛け算、XOR は足し算とみなせる。実際、各桁ごとにみると、次のようになっている。

AND は、mod 2 世界での掛け算になっている
XOR は、mod 2 世界での足し算になっている (mod 2 では 1 + 1 = 0 になる)

AND	0	1
0	0	0
1	0	1

XOR	0	1
0	0	1
1	1	0

よって、掛け算と足し算の記号を使うと、漸化式は

$a_{i+K} = C_{1} \times a_{i+K-1} + C_{2} \times a_{i+K-2} + \dots + C_{K} \times a_{i}$

となる。これはごく普通の漸化式だ。漸化式の第 $M$ 項は行列累乗によって効率的に求められることが知られている。

この漸化式は、次のように行列で表せる。ここで、行列演算における「掛け算」の部分は AND、「足し算」の部分は XOR を表しているものとする。

$\begin{bmatrix} a_{i+1} \\ a_{i+2} \\ \vdots \\ a_{i+K-1} \\ a_{i+K} \\ \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ C_{K} & C_{K-1} & C_{K-2} & \cdots & C_{1} \\ \end{bmatrix} \begin{bmatrix} a_{i} \\ a_{i+1} \\ \vdots \\ a_{i+K-2} \\ a_{i+K-1} \\ \end{bmatrix}$

よって、

$B = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \cdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ C_{K} & C_{K-1} & C_{K-2} & \cdots & C_{1} \\ \end{bmatrix}$

としたとき、 $B^{M}$ を計算することで、 $a_{M}$ も求められる。計算量は $O(K^{3} \log N)$ となる。

コード

XOR 演算の単位元は、通常の足し算と同じく「0」だが、AND 演算の単位減は、通常の掛け算とは異なり、「111...1 (二進法)」という数であることに注意して実装する。

単位行列も、いつものように対角成分に 1 が並ぶのではなく、111...1 (二進法) を並べる。

#include <bits/stdc++.h>
using namespace std;

// AND 演算の単位元 (普通の掛け算の 1 に相当)
const long long UNIT = (1LL<<50) - 1;

template<class T> struct Matrix {
    vector<vector<T> > val;
    Matrix(int n, int m, T x = 0) : val(n, vector<T>(m, x)) {}
    void init(int n, int m, T x = 0) {val.assign(n, vector<T>(m, x));}
    size_t size() const {return val.size();}
    vector<T>& operator [] (int i) {return val[i];}
};

template<class T> Matrix<T> operator * (Matrix<T> A, Matrix<T> B) {
    Matrix<T> R(A.size(), B[0].size());
    for (int i = 0; i < A.size(); ++i)
        for (int j = 0; j < B[0].size(); ++j)
            for (int k = 0; k < B.size(); ++k)
                R[i][j] ^= (A[i][k] & B[k][j]);
    return R;
}

template<class T> vector<T> operator * (Matrix<T> A, vector<T> B) {
    vector<T> v(A.size());
    for (int i = 0; i < A.size(); ++i)
        for (int k = 0; k < B.size(); ++k)
            v[i] ^= (A[i][k] & B[k]);
    return v;
}

template<class T> Matrix<T> pow(Matrix<T> A, long long n) {
    Matrix<T> R(A.size(), A.size());
    for (int i = 0; i < A.size(); ++i) R[i][i] = UNIT;
    while (n > 0) {
        if (n & 1) R = R * A;
        A = A * A;
        n >>= 1;
    }
    return R;
}

int main() {
    long long K, M;
    cin >> K >> M;
    --M;
    vector<long long> A(K), C(K);
    for (int i = 0; i < K; ++i) cin >> A[i];
    for (int i = 0; i < K; ++i) cin >> C[i];
    
    if (M < K) {
        cout << A[M] << endl;
        return 0;
    }
    
    Matrix<long long> mat(K, K, 0);
    for (int i = 0; i < K; ++i) {
        mat[K-1][i] = C[K-1-i];
        if (i < K-1) mat[i][i+1] = UNIT;
    }
    vector<long long> res = pow(mat, M) * A;
    cout << res[0] << endl;
}

別解

きたまさ法や、Bostan-Mori 法も適用できる。

多項式演算を愚直に実装した場合、これらの解法は $O(K^{2} \log N)$ となる。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 009 D - 漸化式 (試験管黄色)

問題概要

制約

考えたこと

コード

別解