Submission #3818715
Source Code Expand
//Night's template
//orzakyrt
#include <bits/stdc++.h>
#define R register
#define LL long long
#ifdef __DEBUG__
#define Debug (fprintf(stderr,"orzyrt\n"),fflush(stderr))
#define debug(__a...) (fprintf(stderr,__a),fflush(stderr))
#define setfile(__a) ('orzyrt')
#define Compile(__a) system("g++ "__a".cpp -lm -o "__a)
#else
#define Debug ('orzyrt')
#define debug(__a...) ('orzyrt')
#define setfile(__a) freopen(__a".in","r",stdin);freopen(__a".out","w",stdout)
#define Compile(__a) ('orzyrt')
#endif
template<class TT>inline TT Max(R TT a,R TT b){return a<b?b:a;}
template<class TT>inline TT Min(R TT a,R TT b){return a<b?a:b;}
template<class TT>inline TT Abs(R TT a){return a<0?-a:a;}
template<class TT>inline TT cmin(R TT &a,R TT b){(b<a)&&(a=b);}
template<class TT>inline TT cmax(R TT &a,R TT b){(a<b)&&(a=b);}
using namespace std;
template<class TT>inline void read(R TT &x){
x=0;R bool f=false;R char c=getchar();
for(;c<48||c>57;c=getchar())f|=(c=='-');
for(;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
(f)&&(x=-x);
}
//end template
namespace Night{
const int mod = 1e9+7;
struct mat{
int a[3][3];
inline mat operator * (R const mat &x)const{
static mat c;memset(c.a,0,sizeof c.a);
for(R int i=0;i<3;++i)
for(R int j=0;j<3;++j)
for(R int k=0;k<3;++k)
c.a[i][k]=(c.a[i][k]+1ll*a[i][j]*x.a[j][k])%mod;
return c;
}
}A[33],base;
int b[3],c[3];
void mul(R const mat&m){
for(R int i=0;i<3;++i)c[i]=b[i],b[i]=0;
for(R int i=0;i<3;++i)
for(R int j=0;j<3;++j)
b[i]=(b[i]+1ll*m.a[i][j]*c[j])%mod;
}
int n,m;
int main(){
read(n);read(m);
*A=(mat){{{1,0,1},{1,1,1},{1,2,2}}};
base=(mat){{{0,mod-2,mod-1},{1,1,1},{1,2,2}}};
for(R int i=1;i<32;++i)A[i]=A[i-1]*A[i-1];
b[0]=1;
R int x=0,y;
while(m--){
read(y);
for(int i=30;~i;i--)if(y-x-1>>i&1)mul(A[i]);
mul(base);x=y;
}
for(R int i=30;~i;i--)if(n-x>>i&1)mul(A[i]);
cout<<b[2];
return 0;
}
}
int main(){
return Night::main();
}
Submission Info
Submission Time |
|
Task |
E - Placing Squares |
User |
Night |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2037 Byte |
Status |
AC |
Exec Time |
33 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
Status |
|
|
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 |
12 ms |
256 KB |
subtask_1_02.txt |
AC |
4 ms |
256 KB |
subtask_1_03.txt |
AC |
4 ms |
256 KB |
subtask_1_04.txt |
AC |
8 ms |
256 KB |
subtask_1_05.txt |
AC |
33 ms |
256 KB |
subtask_1_06.txt |
AC |
33 ms |
256 KB |
subtask_1_07.txt |
AC |
13 ms |
256 KB |
subtask_1_08.txt |
AC |
13 ms |
256 KB |
subtask_1_09.txt |
AC |
2 ms |
256 KB |
subtask_1_10.txt |
AC |
1 ms |
256 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_12.txt |
AC |
1 ms |
256 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
1 ms |
256 KB |
subtask_1_15.txt |
AC |
1 ms |
256 KB |
subtask_1_16.txt |
AC |
1 ms |
256 KB |
subtask_1_17.txt |
AC |
4 ms |
256 KB |
subtask_1_18.txt |
AC |
8 ms |
256 KB |
subtask_1_19.txt |
AC |
1 ms |
256 KB |
subtask_1_20.txt |
AC |
10 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 |