Submission #2248699


Source Code Expand

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
typedef vector<int>vec;
typedef vector<vec>mat;


int mod_pow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}

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]=(C[i][j]+A[i][k]*B[k][j])%mod;
            }
        }
    }
    return C;
}

mat mat_pow(mat A,int m){
    mat B(A.size(),vec(A.size()));
    for(int i=0;i<A.size();i++)B[i][i]=1;
    while(m){
        if(m&1)B=mul(B,A);
        A=mul(A,A);
        m>>=1;
    }
    return B;
}

signed main(){
    int N,M;
    cin>>N>>M;
    mat a(3,vint(1));
    a[0][0]=1;
    mat A(3,vint(3));
    A[0][0]=2;A[0][1]=1;A[0][2]=1;
    A[1][0]=2;A[1][1]=1;A[1][2]=0;
    A[2][0]=1;A[2][1]=1;A[2][2]=1;

    mat B(3,vint(3));
    B[0][0]=1;B[0][1]=0;B[0][2]=0;
    B[1][0]=2;B[1][1]=1;B[1][2]=0;
    B[2][0]=1;B[2][1]=1;B[2][2]=1;

    int pre=0;
    rep(i,M){
        int x;cin>>x;
        a=mul(mat_pow(A,x-1-pre),a);
        a=mul(B,a);
        pre=x;
    }

    a=mul(mat_pow(A,N-1-pre),a);
    cout<<(a[0][0]+a[1][0]+a[2][0])%mod<<endl;
    return 0;
}

Submission Info

Submission Time
Task E - Placing Squares
User latte0119
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 1786 Byte
Status AC
Exec Time 658 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1600 / 1600
Status
AC × 4
AC × 38
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 201 ms 256 KB
subtask_1_02.txt AC 51 ms 256 KB
subtask_1_03.txt AC 29 ms 256 KB
subtask_1_04.txt AC 74 ms 256 KB
subtask_1_05.txt AC 628 ms 256 KB
subtask_1_06.txt AC 658 ms 256 KB
subtask_1_07.txt AC 126 ms 256 KB
subtask_1_08.txt AC 125 ms 256 KB
subtask_1_09.txt AC 8 ms 256 KB
subtask_1_10.txt AC 6 ms 256 KB
subtask_1_11.txt AC 2 ms 256 KB
subtask_1_12.txt AC 2 ms 256 KB
subtask_1_13.txt AC 3 ms 256 KB
subtask_1_14.txt AC 5 ms 256 KB
subtask_1_15.txt AC 1 ms 256 KB
subtask_1_16.txt AC 2 ms 256 KB
subtask_1_17.txt AC 39 ms 256 KB
subtask_1_18.txt AC 90 ms 256 KB
subtask_1_19.txt AC 1 ms 256 KB
subtask_1_20.txt AC 110 ms 256 KB
subtask_1_21.txt AC 1 ms 256 KB
subtask_1_22.txt AC 1 ms 256 KB
subtask_1_23.txt AC 1 ms 256 KB
subtask_1_24.txt AC 1 ms 256 KB
subtask_1_25.txt AC 1 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 1 ms 256 KB
subtask_1_28.txt AC 1 ms 256 KB
subtask_1_29.txt AC 1 ms 256 KB
subtask_1_30.txt AC 1 ms 256 KB