AtCoder Regular Contest 077D: 11

http://arc077.contest.atcoder.jp/tasks/arc077_b

ARC077に参加。CとEは結構すぐわかった。D解けないのはさすがにまずい。

余事象で考えればすぐわかる。ずっと足し合わせで求めようとして頭がこんがらがった。
でも足し合わせても求められるくらい頭良くしないと。

int N;
int A[MAX_N];
int L, R;
int cnt[MAX_N];

void solve() {
	cin >> N;
	N++;
	rep(i, 0, N + 1) {
		cin >> A[i];
		cnt[A[i]]++;
	}
	int t = -1;
	rep(i, 1, N + 1) {
		if(cnt[i] == 2) t = i;
	}
	int prev = -1;
	rep(i, 0, N + 1) {
		if(t == A[i]) {
			if(prev == -1) {
				prev = i;
				L = prev;
			}
			else {
				R = N - i - 1;
				break;
			}
		}
	}
	fac[0] = 1; fac[1] = 1;
	rep(i, 2, N + 1) {
		fac[i] = fac[i - 1] * i % mod;
	}
	rep(i, 1, N + 1) {
		cout << (C_(N, i) - C_(L + R, i - 1) + mod) % mod << "\n";
	}
}