Submission #1517549

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

const int MAX_N = 100005;
ll fact[MAX_N];
ll factinv[MAX_N];
long long mod_pow(long long x, long long n, long long mod){
	long long res = 1;
	while(n > 0){
		if(n & 1) res = res * x % mod;
		x = x*x % mod;
		n >>= 1;
	}
	return res;
}

//階乗のリストを作る
void make_fact_tbl(long long n, long long mod){
	fact[0] = 1;
	for(long long i=1; i<=n; i++){
		fact[i] = fact[i-1] * i;
		fact[i] %= mod;
	}
}

//階乗の逆元のリストを作る
void make_factinv_tbl(long long n, long long mod){
	factinv[0] = 1; //0の逆元は存在しない
	for(long long i=1; i<=n; i++){
		factinv[i] = mod_pow(fact[i], mod-2, mod);
	}
}

//組み合わせの計算に必要な情報の作成
void comb_init(long long n, long long mod){
	make_fact_tbl(n, mod);
	make_factinv_tbl(n, mod);
}

//組み合わせの計算
long long comb(long long n, long long k, long long mod){
	if(n < k) return 0;
	if(k == 0 || n-k == 0) return 1;
	//printf("n:%lld k:%lld n-k:%lld\n", fact[n], factinv[k], factinv[n-k]);
	return ((fact[n] * factinv[k]) % mod) * factinv[n-k] % mod;
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	int n;
	cin >> n;
	comb_init(n+1, MOD);

	map<int, int> a;
	ll l = -1;
	ll r = -1;
	for(int i=0; i<n+1; i++){
		int t;
		cin >> t;
		if(a.find(t) == a.end()){
			a[t] = i;
		}else{
			l = a[t];
			r = i;
		}
	}

	for(int k=1; k<=n+1; k++){
		ll ans = comb(n+1, k, MOD);
		ans = (ans + MOD - comb(l+n-r, k-1, MOD)) % MOD;
		cout << ans << endl;
	}

	
	return 0;
}

Submission Info

Judge Result