Submission #1607711

---

Source Code Expand

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,1):0;}
template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,1):0;}

ll nextLL() { ll x; cin >> x; return x; }

const ll MOD = 2;

#define SZ(v) ((int)(v).size())
typedef vector<ll> Array;
typedef vector<Array> Matrix;

Matrix zero(int N){ return Matrix(N, Array(N)); }

Matrix identity(int N) {
  Matrix A = zero(N);
  REP(i, N) A[i][i] = 1;
  return A;
}

Array mul(const Matrix &A, const Array &x){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Array y(N);
  REP(i, N) REP(j, M) {
    y[i] += A[i][j] * x[j];
    if (y[i] >= MOD) y[i] %= MOD;
  }
  return y;
}

Matrix mul(const Matrix &A, const Matrix& B) {
  const int N = SZ(A);
  const int P = SZ(A[0]);
  const int M = SZ(B[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) REP(k, P) {
    C[i][j] += A[i][k] * B[k][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

Matrix pow(Matrix A, ll b) {
  Matrix C = identity(SZ(A));
  while (b > 0) {
    if ((b & 1) == 1) C = mul(C, A);
    A = mul(A, A);
    b >>= 1;
  }
  return C;
}

int g = 0;
int main2() {
  int K = (int)nextLL();
  int M = (int)nextLL();
  vector<ll> A(K), C(K);
  REP(i, K) A[i] = nextLL();
  REP(i, K) C[i] = nextLL();

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

  ll ans = 0;
  for (int bit = 0; bit < 32; bit++) {
    Matrix P = zero(K);

    REP(i, K - 1) P[i][i+1] = 1;
    REP(j, K) P[K-1][j] = (C[K - 1 - j] >> bit) & 1;

    Array a = Array(K);
    REP(i, K) a[i] = (A[i] >> bit) & 1;
    P = pow(P, M - K);
    a = mul(P, a);
    ans |= a[K-1] * (1LL << bit);
  }
  cout << ans << endl;
  return 0;
}

int main() {
  for ( ; !cin.eof(); cin >> ws) main2();
  return 0;
}

Submission Info

Judge Result