Submission #1841611


Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

vector<ll> fact(100005), fact_inv(100005);
vector<int> appear(100005, 0);
int l, r;
ll mod = 1e9 + 7;

ll func(ll n, ll p) {
	if (p == 1) return n;
	ll res = func(n, p / 2);
	res *= res;
	res %= mod;
	if (p % 2 == 1) return (res*n)%mod;
	return res;
}

int main() {
	int n; cin >> n;
	ll f = 1;
	fact[0] = fact_inv[0] = 1;
	for (int i = 1; i <= n + 1; ++i) {
		f *= i;
		f %= mod;
		fact.at(i) = f;
		fact_inv.at(i) = func(f, mod - 2);
	}


	for (int i = 1; i <= n; ++i) {
		int a; cin >> a;
		if (appear.at(a) != 0) {
			l = appear.at(a) - 1;
			r = n + 1 - i;
		}
		appear.at(a) = i;
	}

	cout << n << endl;
	for (int k = 2; k <= n; ++k) {
		ll ans = ((fact.at(n + 1) * fact_inv.at(k))%mod * fact_inv.at(n + 1 - k)) % mod;
		if (l + r >= k - 1) ans = (ans + mod - ((fact[l + r] * fact_inv[k - 1]) % mod * fact_inv[l + r - k + 1]) % mod) % mod;
		cout << ans << endl;
	}
	cout << 1 << endl;

	return 0;
}

Submission Info

Submission Time
Task D - 11
User yoshnary
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1196 Byte
Status AC
Exec Time 265 ms
Memory 3200 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 10
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 1.txt, mx.txt, rnd_0.txt, rnd_1.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt AC 265 ms 3200 KB
mx.txt AC 261 ms 3200 KB
rnd_0.txt AC 216 ms 2944 KB
rnd_1.txt AC 187 ms 2944 KB
rnd_2.txt AC 53 ms 2432 KB
rnd_3.txt AC 46 ms 2304 KB
rnd_4.txt AC 79 ms 2432 KB
sample1.txt AC 2 ms 2176 KB
sample2.txt AC 2 ms 2176 KB
sample3.txt AC 2 ms 2176 KB