[AtCoder] ARC 077 D:11

題目連結:http://arc077.contest.atcoder.jp/tasks/arc077_b

---

我賽中的時候蠢蠢的，一直想說要$\binom{n+1}{k}-\sum^{n+1}_{i=1}{\binom{p-1}{i} \times \binom{n+1-q}{n+1-i}}$，後來才發現其實那就等價於$\binom{n+1}{k}-\binom{n-q+p}{k-1}$，其中$p,q$為重複的那兩個數的位置。

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

const int N = 100000 + 5;
const int mod = 1000000007;

int arr[N], pos[N];
lld moni[N], cmb[2][N];
lld qPow(lld,lld);
lld C(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, p, q;cin>>n;
	for(int i=1;i<=n+5;i++) moni[i]=qPow(i, mod-2);
	for(int i=0;i<=n;i++) cin>>arr[i];
	fill(pos, pos+1+n, -1);
	for(int i=0;i<=n;i++){
		if(pos[arr[i]]==-1) pos[arr[i]]=i;
		else{
			p=pos[arr[i]];
			q=i;
			break;
		}
	}
	cmb[0][0]=1;
	cmb[1][0]=1;
	for(int i=1;i<=n+1;i++){
		if(n+1-i+1 >= 1)
			cmb[0][i]=(((cmb[0][i-1]*(lld)(n+1-i+1))%mod)*moni[i])%mod;
		if(n-q+p-i+1 >= 1)
			cmb[1][i]=(((cmb[1][i-1]*(lld)(n-q+p-i+1))%mod)*moni[i])%mod;
	}
	for(int i=1;i<=n+1;i++)
		cout<<(cmb[0][i] - cmb[1][i-1] + mod)%mod<<'\n';
	return 0;
}

lld qPow(lld a, lld b){
	lld r=1;
	while(b){
		if(b&1) r=(r*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return r%mod;
}