2017-10-24

ABC009 - D 漸化式

解説

D - 漸化式

問題概要

二つの数列 A1,A2,,AKA_1, A_2, …, A_KC1,C2,,CKC_1, C_2, …, C_K が入力で与えられる。

数列 A は以下の式によって計算できる。

AN+K=(C1ANDAN+K1)XOR(C2ANDAN+K2)XORXOR(CKANDAN)A_{N+K}=(C_1 AND A_{N+K−1}) XOR (C_2 AND A_{N+K−2}) XOR …  XOR (C_K AND A_N)

数列 A の M 番目の値を求めよ。

解き方

漸化式を計算するには、DPを使えば良いです。しかし、制約が大きく、DPでは解けません。 別の方法を使って漸化式を解く必要があります。

そこで、行列累乗を使います(あり本 P.180参照)。 行列累乗に and や xor が使えるのかですが、それは atcoder の公式解説を参照してください。 あり本を見ながらやれば実装できます。ほとんどあり本のプログラムそのままです。 正しい順番で値を入れて、正しい値で初期化して、演算子を変えましょう。

ただ、割と引っかかるポイントが多かったです。

気をつけるところ

  • and は論理積
    bit の and が取りたい時は、 bitand か & を使いましょう。
  • 各項の順番
    行列に値を入れる際、右から左に並べるのか、左から右に並べるのか(もちろん上下も)。
  • and 演算子の単位元
    普通に掛け算をするのであれば、単位元は 1 です。 あり本にあるプログラムや式は、行列の掛け算を行うため、 単位元に 1 が使われています。 しかし、この問題では and 演算子を使うため、単位元は全 bit が 1 の値です。 初期化ミスに気をつけましょう。
  • m ≤ k の時の処理
    m ≤ k の時は、与えらえれた入力をそのまま返せば良いです。 入力を行列累乗のために逆順に持っていたことを忘れるとWAです(2敗)。

実装

#define int long long なので、単位元は -1 を使っています。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

#define int long long
typedef vector<vector<int>> mat;

mat mul(mat &a, mat &b){
    mat c(a.size(), vector<int>(b[0].size()));
    rep(i,a.size()){
        rep(k,b.size()){
            rep(j,b[0].size()){
                c[i][j] = (c[i][j] xor (a[i][k] bitand b[k][j]));
            }
        }
    }
    return c;
}

mat pow(mat a, int n){
    mat b(a.size(), vector<int>(a.size(),0));
    rep(i,b.size()) b[i][i] = -1;
    while(n > 0){
        if(n & 1) b = mul(b,a);
        a = mul(a, a);
        n >>= 1;
    }
    return b;
}

int solve(int n, mat A, vector<int> c){
    mat a(A.size(), vector<int>(A.size(), 0));
    for(int i = c.size() - 1; i >= 0; i--){
        //a[0][i] = c[A.size() - 1 - i]; ここの順番が逆だった。
        a[0][i] = c[i];
    }
    rep(i,c.size() - 1){
        a[i + 1][i] = -1;
    }

    a = pow(a,n); //行列Aのn乗。
    mat res = mul(a, A);
    return res[0][0];
}

signed main(){
    int k, m;
    cin >> k >> m;

    mat a(k, vector<int>(1));
    vector<int> c(k);
    rep(i,k) cin >> a[k - i - 1][0];
    rep(i,k) cin >> c[i];

    if(m <= k){
        cout << a[k - m][0] << endl;
    }else{
        cout << solve(m - k,a,c) << endl; //-kを忘れずに
    }
}