Submission #1691565


Source Code Expand

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;
typedef long long LL;
const int maxn = 1000005;
const int mod = 1e9+7;

LL dp[maxn],s[maxn],ans;int n;
int main()
{
	#ifdef Amberframe
		freopen("arc071f.in","r",stdin);
		freopen("arc071f.out","w",stdout);
	#endif
	
	scanf("%d",&n);
	dp[0]=s[0]=1;ans=1;
	for (int i=1;i<=n;i++) {
		dp[i]=((i>=3?s[i-3]:0)+dp[i-1])%mod;
		s[i]=(s[i-1]+dp[i])%mod;
	}
	LL w=(LL)(n-1)*(n-1)%mod;
	for (int i=1;i<=n;i++) {
		if (i>=4) ans=(ans+s[i-4])%mod;
		if (i==n) {
			ans=(ans+dp[i-1]*(n-1))%mod;
		}
		else if (i==n-1) {
			ans=(ans+dp[i-1]*(n-1))%mod;
			ans=(ans+dp[i-1]*w)%mod;
		}
		else {
			ans=(ans+dp[i-1]*(LL)(i+1))%mod;
			ans=(ans+dp[i-1]*w)%mod;
		}
	}
	printf("%lld",ans);
	return 0;
}

Submission Info

Submission Time
Task F - Infinite Sequence
User Amberframe
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 828 Byte
Status AC
Exec Time 23 ms
Memory 15872 KB

Compile Error

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

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 16 ms 14592 KB
max_1000000.txt AC 23 ms 15872 KB
max_999745.txt AC 23 ms 15872 KB
max_999880.txt AC 23 ms 15872 KB
max_999999.txt AC 23 ms 15872 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 11 ms 10496 KB
rnd_407774.txt AC 11 ms 10496 KB
rnd_52228.txt AC 3 ms 4736 KB
rnd_68.txt AC 2 ms 2304 KB
rnd_804783.txt AC 20 ms 14592 KB
rnd_85984.txt AC 4 ms 4992 KB
rnd_894324.txt AC 21 ms 15104 KB
rnd_93.txt AC 2 ms 2304 KB
rnd_963981.txt AC 23 ms 15616 KB
rnd_968416.txt AC 23 ms 15616 KB