Submission #2077653


Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long nagai;

const nagai mod = 1000000007;

void md(nagai& x)
{
	if (x >= mod)
		x -= mod;
}

int main()
{
	int n; 
	cin >> n;
	vector<nagai> cnt(n + 1);
	cnt[0] = 1;
	cnt[1] = n;
	nagai cursum = 0;
	for (int i = 2; i <= n; ++i)
	{
		md(cnt[i] += cnt[i - 1]);
		(cnt[i] += 1LL * (n - 2 + 1) * (n - 1)) %= mod;
		int cnt0 = (n - 2 + 1) - (i - 3 - 0 + 1);
		md(cnt[i] += cnt0);
		md(cnt[i] += cursum);
		md(cursum += cnt[i - 2]);
		//for (int k = 2; k <= n; ++k)
			//md(cnt[i] += cnt[max(0, i - k - 1)]);
		//cerr << cnt[i] << ' ';
	}
	//cerr << endl;
	cout << cnt.back() << endl;

}

Submission Info

Submission Time
Task F - Infinite Sequence
User scanhex
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 680 Byte
Status AC
Exec Time 13 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 9 ms 5376 KB
max_1000000.txt AC 13 ms 8064 KB
max_999745.txt AC 13 ms 8064 KB
max_999880.txt AC 13 ms 8064 KB
max_999999.txt AC 13 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 6 ms 3200 KB
rnd_407774.txt AC 7 ms 3456 KB
rnd_52228.txt AC 2 ms 640 KB
rnd_68.txt AC 1 ms 256 KB
rnd_804783.txt AC 11 ms 6528 KB
rnd_85984.txt AC 2 ms 896 KB
rnd_894324.txt AC 12 ms 7296 KB
rnd_93.txt AC 1 ms 256 KB
rnd_963981.txt AC 13 ms 7808 KB
rnd_968416.txt AC 13 ms 7808 KB