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