Submission #2981606


Source Code Expand

#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

typedef long long ll;
ll n,A[1000050];
int main(){
	cin >> n;
	A[1] = n; A[1] %= mod;
	ll ans = A[1];
	for(ll i = 2; i<=n; i++){
		A[i] = A[i-1];
		A[i]%=mod;
		A[i] += ((n-1)*(n-1))%mod;
		A[i]%=mod;
		if(2 <= i-2) A[i] += ans-A[i-1]-A[i-2];
		A[i] %= mod;
		A[i] += n-max((ll)2, i-1)+1; 
		A[i]%=mod;
		A[i]+=mod;
		A[i]%=mod;
		ans += A[i];
		ans %= mod;
	}
	cout << A[n];
}
/*
f(x) =
case: 1____
f(x-1)
case: YXX.. X!=1, Y!=1
(n-1)^2
case: Y111__, x-Y-1 > 0
f(x-Y-1) from Y=2 to Y=x-2, hence f(x-3) to f(1)
case: Y111.., x-1 <= Y
Y can vary from Y=2 to x-2 and from x-1 to N
hence N-x+2
*/

Submission Info

Submission Time
Task F - Infinite Sequence
User tch1001
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 704 Byte
Status AC
Exec Time 21 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 256 KB
0_001.txt AC 14 ms 6400 KB
max_1000000.txt AC 21 ms 8064 KB
max_999745.txt AC 21 ms 8064 KB
max_999880.txt AC 21 ms 8064 KB
max_999999.txt AC 21 ms 8064 KB
min_1.txt AC 1 ms 256 KB
rnd_14.txt AC 1 ms 256 KB
rnd_22.txt AC 1 ms 256 KB
rnd_25002.txt AC 2 ms 384 KB
rnd_2956.txt AC 1 ms 256 KB
rnd_3.txt AC 1 ms 256 KB
rnd_380467.txt AC 9 ms 4352 KB
rnd_407774.txt AC 10 ms 4352 KB
rnd_52228.txt AC 2 ms 640 KB
rnd_68.txt AC 1 ms 256 KB
rnd_804783.txt AC 17 ms 6528 KB
rnd_85984.txt AC 3 ms 896 KB
rnd_894324.txt AC 19 ms 7168 KB
rnd_93.txt AC 1 ms 256 KB
rnd_963981.txt AC 20 ms 7808 KB
rnd_968416.txt AC 20 ms 7808 KB