ABC 009 D-漸化式
問題:D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
参考:Abc009
まず、ビット演算をそれぞれ非負の整数に対し
XOR(^)->足し算っぽいもの AND(&)->掛け算っぽいもの
とみなすことでこれらを用いて普通の行列と同様の方法で演算を行うことができる。
ここでの足し算っぽさ、掛け算っぽさは半環の性質によって与えられる(?)。(抽象代数学について学べばこの辺りの理論に詳しくなれそう)
あとは、AND演算に対する単位元が1でなく2^n-1(nは十分に大きい整数)(二進数で全ての桁が1)であることに注意すれば通常の行列の演算が使える。
そして、漸化式を行列を用いて表して、その公比っぽい行列を累乗して、初項っぽいベクトルを掛けることで答えが求まる。
行列の累乗には繰り返し二乗法を用いる
計算量は行列積にO(K^3)m乗の計算にO(log m)かかるので
全体としてO(K^3 log m)
#include<iostream> #include<vector> #include<limits.h> using namespace std; typedef vector<unsigned int>vec; typedef vector<vec> mat; mat mul(mat& A,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 pow(mat A,int n){ mat B(A.size(),vec(A.size())); for(int i=0;i<A.size();i++){ B[i][i]=UINT_MAX; } while(n>0){ if(n&1)B=mul(B,A); A=mul(A,A); n>>=1; } return B; } int main(){ int k,m; cin>>k>>m; mat A(k,vec(1)); for(int i=0;i<k;i++){ cin>>A[k-i-1][0]; } mat B(k,vec(k)); for(int i=0;i<k;i++){ cin>>B[0][i]; } for(int i=0;i+1<k;i++)B[i+1][i]=UINT_MAX; B=pow(B,m-1); A=mul(B,A); cout<<A[k-1][0]<<endl; }