Submission #3413692

---

Source Code Expand

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)
#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

VV mul(VV &a, VV &b){
    VV c(a.size(),V(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;
}

VV power(VV a, int n){
    VV b(a.size(), V(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, VV A, V C){
    
    VV a(A.size(), V(A.size(),0));
    
    rrep(i,C.size()-1){
        a[0][i] = C[i];
    }
    
    rep(i,C.size()-1){
        a[i+1][i] = -1;
    }
    
    a = power(a,n);
    VV res = mul(a,A);
    return res[0][0];
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int K, M;
    cin>>K>>M;
    
    VV A(K,V(1));
    V C(K);
    rep(i,K) cin>>A[K-i-1][0];
    rep(i,K) cin>>C[i];
    
    if(M<=K){
        cout1(A[K-M][0]);
    }else{
        cout1(solve(M-K,A,C));
    }
}

Submission Info

Judge Result