AtCoder ARC #077 : D - 11

Eでミス連発、Fが時間切れで微妙な順位に。
http://arc077.contest.atcoder.jp/tasks/arc077_b

問題

1～Nで構成される長さ(N+1)の数列Aが与えられる。
1～NはA中最低1回は現れる。
B(i) := Aの長さiの部分列のうちユニークなものの数
とするとき、B(1)～B(N+1)を求めよ。

解法

A中1種類だけ2回登場する数値がある。
そのような数値のindexをp,qとする(A[p]=A[q])

B(i)を求める際、部分列にA[p]が何回登場するかに応じてそれぞれ場合分けしていこう。

• A[p]を含まない場合
  • A[p]以外の(N-1)要素からi要素を選ぶので通り。
• A[p]を1個だけ含む場合
  • A[p+1]～A[q-1]から1個も選ばない場合
    • この場合A[p]とA[q]どちらから選んだかは考慮されない(同じ結果になる)
    • よってA[0]～A[p-1]とA[q+1]～A[N-1]から(i-1)個選ぶので通り。
  • A[p+1]～A[q-1]から1個以上選ぶ場合
    • A[p]とA[q]どちらから選んだかで得られる部分列が異なる。
    • A[p+1]～A[q-1]から1個以上選ぶ場合は、全体から選ばない例を引けばいいので通り。
• A[p]、A[q]をともに含む場合
  • 残り(N-1)から(i-2)個選ぶので通り。

ll mo=1000000007;
ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

int N;
int A[101010];
int num[101010];
vector<int> V;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+1) {
		cin>>A[i];
		num[A[i]]++;
	}
	FOR(i,N+1) if(num[A[i]]==2) V.push_back(i);
	int a=V[0];
	int b=V[1]-V[0]-1;
	int c=N-V[1];
	for(i=1;i<=N+1;i++) {
		if(i==1) {
			cout<<N<<endl;
			continue;
		}
		ll ret=0;
		// D=0
		ret += combi(N-1,i);
		// D=1
		ret += combi(a+c,i-1);
		ret += (combi(a+c+b,i-1)-combi(a+c,i-1))*2;
		
		// D=2
		ret += combi(N-1,i-2);
		
		cout<<(ret%mo+mo)%mo<<endl;
		
	}
	
	
}

まとめ

まぁこれはすんなり。