Submission #1725062


Source Code Expand

Copy
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 1e+6+5;
const int mo = 1e+9+7;


int f[N],pre[N];
int n;

int add(int x,int y){return x+y>=mo?x+y-mo:x+y;}

int main(){
	n=get();
	f[0]=1;
	pre[0]=1;
	fo(i,1,n){
		if (i>=3)f[i]=pre[i-3];
		f[i]=add(f[i],f[i-1]);
		pre[i]=add(pre[i-1],f[i]);
	}
	LL ans=(1ll*f[n]+1ll*f[n-1]*(n-1)%mo)%mo;
	fo(i,0,n-2)ans=(ans+1ll*f[i]*(n-1)%mo*(n-1)%mo)%mo;
	fo(i,0,n-2)ans=(ans+1ll*f[i]*(i+1)%mo)%mo;
	printf("%lld\n",ans);
	return 0;
}

Submission Info

Submission Time
Task F - Infinite Sequence
User samjia2000
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1013 Byte
Status AC
Exec Time 16 ms
Memory 8064 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 22
Set Name Test Cases
Sample 0_000.txt, 0_001.txt
All 0_000.txt, 0_001.txt, max_1000000.txt, max_999745.txt, max_999880.txt, max_999999.txt, min_1.txt, rnd_14.txt, rnd_22.txt, rnd_25002.txt, rnd_2956.txt, rnd_3.txt, rnd_380467.txt, rnd_407774.txt, rnd_52228.txt, rnd_68.txt, rnd_804783.txt, rnd_85984.txt, rnd_894324.txt, rnd_93.txt, rnd_963981.txt, rnd_968416.txt
Case Name Status Exec Time Memory
0_000.txt AC 2 ms 2304 KB
0_001.txt AC 11 ms 6656 KB
max_1000000.txt AC 16 ms 8064 KB
max_999745.txt AC 16 ms 8064 KB
max_999880.txt AC 16 ms 8064 KB
max_999999.txt AC 16 ms 8064 KB
min_1.txt AC 2 ms 2304 KB
rnd_14.txt AC 2 ms 2304 KB
rnd_22.txt AC 2 ms 2304 KB
rnd_25002.txt AC 2 ms 2432 KB
rnd_2956.txt AC 2 ms 2304 KB
rnd_3.txt AC 2 ms 2304 KB
rnd_380467.txt AC 8 ms 5760 KB
rnd_407774.txt AC 8 ms 5888 KB
rnd_52228.txt AC 3 ms 4608 KB
rnd_68.txt AC 2 ms 2304 KB
rnd_804783.txt AC 14 ms 7296 KB
rnd_85984.txt AC 4 ms 4736 KB
rnd_894324.txt AC 15 ms 7680 KB
rnd_93.txt AC 2 ms 2304 KB
rnd_963981.txt AC 16 ms 7936 KB
rnd_968416.txt AC 16 ms 7936 KB