Submission #1868624

---

Source Code Expand

#include <iostream>
#define REP(i,N) for(int i = 0; i < (N); ++i)
using namespace std;

const int MAX_N = 1e5 * 2;
typedef long long ll;
const int MOD = 1e9 + 7;
ll ifact[MAX_N];
ll fact[MAX_N];

ll comb(int n, int k){
  return fact[n] * ifact[k] % MOD * ifact[n-k] % MOD;
}
ll mod_pow(ll n, ll x){
  ll res = 1;
  while(n > 0){
    if(n & 1) res = res * x % MOD;
    x = x * x % MOD;
    n >>= 1;
  }
  return res;
}

void inv_fact(int M){
  fact[0] = ifact[0] = 1;
  for(int i = 1; i <= M; i++){
    fact[i] = fact[i-1] * i % MOD;
  }
  ifact[M] = mod_pow(MOD - 2, fact[M]);
  for(int i = M - 1; i >= 1; i--){
    ifact[i] = ifact[i + 1] * (i + 1) % MOD;
  }
}
int used[100005];
int main(){
  int N;
  cin >> N;
  N++;
  inv_fact(N);
  int a[100005];
  int overlap_i, overlap_j;
  REP(i,N){
    cin >> a[i];
    if(!used[a[i]]) used[a[i]] = i + 1;
    else{
      overlap_i = used[a[i]];
      overlap_j = i + 1;
    }
  }
  for(int el_n = 1; el_n <= N; el_n++){
    ll ans = comb(N, el_n);
    if(el_n == 1){
      cout << ans - 1 << endl;
      continue;
    }
    int overlap_seq_ct = (N - overlap_j) + (overlap_i - 1);
    if(overlap_seq_ct >= el_n - 1){
      ans = (ans - comb(overlap_seq_ct, el_n - 1) + MOD) % MOD;
    }
    cout << ans << endl;
  }
  return 0;
}

Submission Info

Judge Result