ABC066 ARC077 D - 11

問題のリンク

D - 11

考察

ほとんどの要素が異なるので、異なる場所から取り出した部分列は大体異なる。同じになるパターンを数えるのが速そう。

同じになるパターンに関係してくるのはa[i] = a[j] ( i j ) を満たすもの。そのようなi, j と他の要素を区別して、図のようにする

k = 2 のとき
数列から2 つ選んでくるパターンで、({A内の要素}, a[i]) と ({A内の要素}, a[j]) や(a[i], {C内の要素}) と(a[j], {C内の要素}) という選び方をすると、取り出した要素のインデックスの組は異なるのに、部分列は同じになる。このような取り出し方は、Aの要素の数を|A| のように表して、|A| + |C| である。

一般的なk について

数列からk 個選んでくるパターンで、取り出した要素のインデックスが異なり、部分列が同じになる取り出し方は、({A内の要素からx 個} , a[i], {C内の要素からk-x 個} ) と({A内の要素からx 個} , a[j], {C内の要素からk-x 個} ) みたいなパターン。これらの総数は、 * となる。

wolframalphaによると、 * = となる。

便利なものに頼らずとも、上の取り出し方は、AとCを合わせたものからk 個選んでくる。という取り出し方に等しいので、 とすれば良い。

実装

#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
const ll MOD=1e+9+7;
struct mint{
  ll x;
  mint(ll x=0):x(x%MOD){}
  mint& operator+=(const mint a){
    if((x+=a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x += MOD-a.x)>=MOD) x-=MOD;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=MOD;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a = pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }
  
  //for prime mod
  mint inv() const{
    return pow(MOD-2);
  }
  mint& operator/=(const mint a){
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};

const int NMAX=200010; // we can calculate nCk until n is equal to NMAX
mint fact[NMAX],infac[NMAX];
void Make_Fact(){
  fact[0]=fact[1]=1;
  for(int i=2;i<=NMAX-1;++i){
    fact[i]=fact[i-1]*(mint)i;
  }
}
void Make_InvFact(){
  infac[0]=infac[1]=1;
  for(int i=2;i<=NMAX-1;++i){
    infac[i]=infac[i-1]/(mint)i;   
  }
}
mint Comb(int n,int k){
  if(n<0||k<0||n-k<0) return 0;
  return fact[n]*infac[k]*infac[n-k];
}



int main()
{
  int n; cin >> n;
  vector<int> a(n+1);
  rep(i,n+1) cin >> a[i];

  vector<int> st(n+1, 0);
  int piv;
  rep(i,n+1) {
    if(st[a[i]] == 1) piv = i;
    st[a[i]]++;
  }
  int m = n - piv;  
  rep(i,n+1) {
    if(st[a[i]] == 2) {
      piv = i;
      break;
    }
  }
  int k = piv;
  
  Make_Fact();
  Make_InvFact();
  rep1(i,n+1) {
    mint res = Comb(n+1, i) - Comb(k+m, i-1);
    cout << res.x << "\n";
  }
  
  
  return 0;
}