ゆらのふなびと

競プロ, Python, C++

ABC009 D - 漸化式

行列累乗は半環なら普通の演算以外でも使えるよ!という問題。

問題

数列 A はすべての要素が 32 ビットの符号なし整数で表現でき、その値は次のようにして決まる。

  • はじめの K 項 A1, A2, …, AK は入力で与えられる。
  • A とは別に K 項の数列 C1, C2, …, CK (こちらもすべての要素が 32 ビットの符号なし整数におさまる)が入力で与えられ、K+1 項目以降の A の値はこの C を用いて次のように計算される。
    • N≧1 に対し AN+K=(C1 AND AN+K−1) XOR (C2 AND AN+K−2) XOR …  XOR (CK AND AN)
    • ただし AND はビットごとの論理積、 XOR はビットごとの排他的論理和を表す。

この数列 A の M 番目の値 AM を求めるプログラムを作成せよ。

制約

 1 \leq K \leq 100

 1 \leq M \leq 10^9

解法

行列累乗。この問題では足し算をXOR, 掛け算をANDとみなせば適用できる。ただし掛け算の単位元が11111...となることに注意。

typedef unsigned long long ull;

typedef vector<ull> vec;
typedef vector<vec> mat;
#define ULL_MAX 4294967295

const int MAX_LOG = 40;
mat F[MAX_LOG];

mat mulMatMat(mat a, mat b) {
    int arow = a.size();
    int acol = a[0].size();
    int bcol = b[0].size();
    mat c(arow, vec(bcol, 0));
    rep(i, arow) {
        rep(j, bcol) {
            rep(k, acol) {
                c[i][j] ^= (a[i][k] & b[k][j]);
            }
        }
    }
    return c;
}

vec mulMatVec(mat a, vec b) {
    int arow = a.size();
    int acol = a[0].size();
    vec c(arow, 0);
    rep(i, arow) {
        rep(j, acol) {
            c[i] ^= a[i][j] & b[j];
        }
    }
    return c;
}

signed main() {
    int K, M;
    cin >> K >> M;
    M--;
    vec A(K);
    vec C(K);
    rep(i, K) cin >> A[i];
    rep(i, K) cin >> C[i];

    if (M < K) {
        cout << A[M] << endl;
        return 0;
    }

    mat a(K, vec(K, 0));
    rep(j, K) {
        a[0][j] = C[j];
    }
    rep(i, K - 1) {
        a[i + 1][i] = ULL_MAX;
    }
    F[0] = a;

    rep(i, MAX_LOG - 1) {
        F[i + 1] = mulMatMat(F[i], F[i]);
    }

    reverse(all(A));
    vec t = A;
    rep(i, MAX_LOG) {
        if (M & 1) {
            t = mulMatVec(F[i], t);
        }
        M /= 2;
        if (M <= 0) break;
    }

    reverse(all(t));
    cout << t[0] << endl;
}