ABC 9 D - 漸化式 ( Fast matrix multiplication + XOR / AND property )

D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
I was surprised that this could be matrix multiplication as well.

Abc009 from AtCoder Inc.

www.slideshare.net
According to the slides, when the operation has property of 0, commutative rule and associative rule, somehow alike + and *, it is allowed to be performed with matrix multiplication. In this case, XOR has the property of + and AND has the property of *. The main difference here is how they react when they some non-zero element is performed against 0.
Note that in this case, the identity matrix should be all 1s, which is 0xffffffff, 32 of 1s in binary expression.

#include <bits/stdc++.h>
using namespace std;
const int MAXK = 100 + 2;
const int MAXM = 1e9 + 9;
typedef unsigned int ui;

typedef vector<ui> vec;
typedef vector<vec> mat;

int K, M;
ui A[ MAXK ], C[ MAXK ];

mat mul(const mat &a, const mat &b){
    mat c( a.size(), vec( 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 < a[ 0 ].size(); ++k)
                c[ i ][ j ] ^= a[ i ][ k ] & b[ k ][ j ];
    return c;
}

mat po(mat a, int p){
    mat b( a.size(), vec( a[ 0 ].size() ) );
    for(int i = 0; i < a.size(); ++i)
        b[ i ][ i ] = 0xffffffff; // = 1111 1111 1111 1111 1111 1111 1111 1111 
    while( p > 0 ){
        if( p & 1 ) b = mul( b, a );
        a = mul( a, a );
        p >>= 1;
    }       
    return b;
}

void solve(){
    mat coef( K, vec( K ) );
    for(int i = 0; i < K; ++i)
        coef[ 0 ][ i ] = C[ i ];
    for(int i = 1; i < K; ++i)
        coef[ i ][ i - 1 ] = 0xffffffff;
    mat val( K, vec( 1 ) );
    for(int i = 0; i < K; ++i)
        val[ i ][ 0 ] = A[ i ];
    coef = po( coef, M - 1 );
    val = mul( coef, val );
    cout << val[ K - 1 ][ 0 ] << endl;
}

int main(){
    cin >> K >> M;
    for(int i = 0; i < K; ++i)
        cin >> A[ i ];
    reverse( A, A + K );
    for(int i = 0; i < K; ++i)
        cin >> C[ i ];
    solve();
    return 0;
}