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