Submission #1841607

---

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;
		for (int t = 0; t <= k - 1; ++t) {
			if (l < t) break;
			if (r < k - 1 - t) continue;
			ll d = ((fact.at(l) * fact_inv.at(t)) % mod *fact_inv.at(l - t)) % mod;
			d *= ((fact.at(r) * fact_inv.at(k - 1 - t)) % mod * fact_inv.at(r - k + 1 + t)) % mod;
			d %= mod;
			ans = (ans + mod - d) % mod;
		}
		cout << ans << endl;
	}
	cout << 1 << endl;

	return 0;
}

Submission Info

Judge Result