Submission #1841602

---

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;

ll fact[100005], fact_inv[100005];
int a[100004];
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[i] = f;
		fact_inv[i] = func(f, mod - 2);
	}

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

	cout << n << endl;
	for (int k = 2; k <= n; ++k) {
		ll ans = ((fact[n + 1] * fact_inv[k])%mod * fact_inv[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[l] * fact_inv[t]) % mod *fact_inv[l - t]) % mod;
			d *= ((fact[r] * fact_inv[k - 1 - t]) % mod * fact_inv[r - k + 1 + t]) % mod;
			d %= mod;
			ans = (ans + mod - d) % mod;
		}
		cout << ans << endl;
	}
	cout << 1 << endl;

	return 0;
}

Submission Info

Judge Result