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
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 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