Submission #1514886
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define mod 1000000007 ll dp[1000005],ret; int main(){ int n; cin >> n; for(int i=0;i<=n;i++) dp[i] = 1LL; ll add = 0LL,sum = 0LL; for(int i=3;i<=n;i++){ add+=sum; add+=dp[i-3]; add%=mod; sum+=dp[i-3]; sum%=mod; dp[i]=(dp[i]+add)%mod; } ret = dp[n]+dp[n-1]*1LL*(n-1)%mod; for(int i=0;i<n-1;i++){ ret += dp[i]*1LL*(n-1)%mod*(n-1)%mod; ret += dp[i]*1LL*(i+1)%mod; } cout << ret%mod << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Infinite Sequence |
User | IH19980412 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 989 Byte |
Status | AC |
Exec Time | 14 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 | 1 ms | 256 KB |
0_001.txt | AC | 10 ms | 6400 KB |
max_1000000.txt | AC | 14 ms | 8064 KB |
max_999745.txt | AC | 14 ms | 8064 KB |
max_999880.txt | AC | 14 ms | 8064 KB |
max_999999.txt | AC | 14 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 | 7 ms | 4352 KB |
rnd_407774.txt | AC | 7 ms | 4352 KB |
rnd_52228.txt | AC | 2 ms | 640 KB |
rnd_68.txt | AC | 1 ms | 256 KB |
rnd_804783.txt | AC | 12 ms | 6528 KB |
rnd_85984.txt | AC | 2 ms | 896 KB |
rnd_894324.txt | AC | 13 ms | 7168 KB |
rnd_93.txt | AC | 1 ms | 256 KB |
rnd_963981.txt | AC | 14 ms | 7808 KB |
rnd_968416.txt | AC | 14 ms | 7808 KB |