Submission #1771061

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;
 
template <class T> struct SquareMatrix {

    vector < vector < T > > mat;
    SquareMatrix (int n) : mat(n, vector < T > (n, 0)) {}
    
    vector < T > & operator [] (int n) {
        return mat[n];
    }
    
    int size() {
        return (int) mat.size();
    }

    void operator = (SquareMatrix A) {
        for (int i = 0; i < mat.size(); i++)
            for (int j = 0; j < mat.size(); j++)
                this -> mat[i][j] = A[i][j];
    }
        
};

template <class Matrix> Matrix operator + (Matrix &A, Matrix &B) {
    Matrix ret(A.size());
    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < A.size(); j++)
            ret[i][j] = A[i][j] + B[i][j];
    return ret;
}

template <class Matrix, class Vector> Vector operator * (Matrix &M, Vector &V) {
    Vector ret(V.size(), 0);
    if (M.size() != V.size()) return {-1};
    for (int i = 0; i < M.size(); i++)
        for (int j = 0; j < M.size(); j++)
            ret[i] += M[i][j] * V[j];
    return ret;
}

template <class Matrix> Matrix operator * (Matrix &A, Matrix &B) {
    Matrix ret(A.size());
    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < A.size(); j++)
            for (int k = 0; k < A.size(); k++)
                ret[i][j] += A[i][k] * B[k][j];
    return ret;
}   

void pow_mod_matrix(SquareMatrix <long long > &M, long long k) {
    SquareMatrix < long long > A = M; 
    k--;
    while (k > 0) {
        if (k & 1) M = (M * A);
        A = A * A;
        k >>= 1;
    }
}
 
int main() {
 
    ll N,M; cin >> N >> M;
    vector < long long > A(N),C(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> C[i];
 
    SquareMatrix < long long > Mat(N);
    REP(i,N) Mat[0][i] = C[i];
    REP(i,N - 1) REP(j,N) {
        if (i == j) Mat[i + 1][j] = -1LL;
        else Mat[i + 1][j] = 0;        
    }
 
    if (M <= N) {
        cout << A[M - 1] << endl;
        return 0;
    }
 
    M -= N;
 
    pow_mod_matrix(Mat, M);
 
    reverse(A.begin(), A.end());
    vector < long long > ans = Mat * A;
 
    cout << ans[0] << endl;
 
    return 0;
}

Submission Info

Judge Result