Submission #1691610


Source Code Expand

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const long long md=1e9+7;
struct node{
	long long a[3][3];
	void print(){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++)
				printf("%lld ",a[i][j]);
			printf("\n");
		}
		printf("\n");
	}
	void mem(){
		memset(a,0,sizeof(a));
	}
	void csh(){
		mem();
		for(int i=0;i<3;i++)
			a[i][i]=1;
	}
	void bebase(){
		mem();
		a[0][1]=1,a[1][2]=1;
		a[2][0]=1,a[2][1]=md-2,a[2][2]=4;
	}
}base;
node operator * (const node &A,const node &B){
	node res;
	res.mem();
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++)
				res.a[i][j]+=A.a[i][k]*B.a[k][j]%md;
			res.a[i][j]%=md;
		}
	return res;
}
node powd(node x,int y){
	node res;
	res.csh();
	while(y){
		if(y&1) res=res*x;
		x=x*x;
		y>>=1;
	}
	return res;
}
long long getval(const node &A){
	return (1*A.a[0][1]+5*A.a[0][2])%md;
}
int a[100100];
int main(){
//	freopen("E.in","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",&a[i]);
	a[++m]=n;
	base.bebase();
	node tot,st;
	tot.mem();
	long long ans;
	for(int i=1;i<=m;i++)
	{
		st=powd(base,a[i]-a[i-1]);
		tot=tot*st;
		ans=(getval(powd(base,a[i]))-getval(tot)+md)%md;
//		printf("%lld\n",ans);
		for(int j=0;j<3;j++)
			(tot.a[j][j]+=ans)%=md;
	}
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Submission Time
Task E - Placing Squares
User xzkflowey
Language C++14 (GCC 5.4.1)
Score 1600
Code Size 1386 Byte
Status AC
Exec Time 610 ms
Memory 640 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
./Main.cpp:60:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

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 190 ms 384 KB
subtask_1_02.txt AC 42 ms 256 KB
subtask_1_03.txt AC 94 ms 384 KB
subtask_1_04.txt AC 253 ms 512 KB
subtask_1_05.txt AC 602 ms 640 KB
subtask_1_06.txt AC 610 ms 640 KB
subtask_1_07.txt AC 435 ms 640 KB
subtask_1_08.txt AC 445 ms 640 KB
subtask_1_09.txt AC 6 ms 256 KB
subtask_1_10.txt AC 5 ms 256 KB
subtask_1_11.txt AC 5 ms 256 KB
subtask_1_12.txt AC 3 ms 256 KB
subtask_1_13.txt AC 3 ms 256 KB
subtask_1_14.txt AC 4 ms 256 KB
subtask_1_15.txt AC 2 ms 256 KB
subtask_1_16.txt AC 4 ms 256 KB
subtask_1_17.txt AC 82 ms 384 KB
subtask_1_18.txt AC 205 ms 512 KB
subtask_1_19.txt AC 1 ms 256 KB
subtask_1_20.txt AC 258 ms 640 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