11 [AtCoder Beginner Contest 066 / AtCoder Regular Contest 077 D]

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

解法

http://arc077.contest.atcoder.jp/submissions/1397459

ダブっている数は1種類だけなので、その数(変数twice)と出て来るindex(変数a,b)を特定しておく。
適当な部分文字列を取ってきて、重複が起きるのは、[0,a)と(b,N]から文字列を選んで、間の数としてa番目を取る場合とb番目を取る場合である。

まず、微妙にバグりそうな最初と最後はちょっと怖いので別途出力しておく。
全ての長さについて、ダブリを含んだ個数を数え上げる。
これはaCb(N + 1, i)である。
あとは、ダブリを引けばいいのだが、[0,a)と(b,N]の個数をcntとしておくと、そのうちi-1個を取る組合せがダブっている組合せであることが分かる。
これをひける場合は引いて答え。

Comb<mint, 201010> com;
int N, A[101010];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N + 1) cin >> A[i];
    rep(i, 0, N + 1) cnt[A[i]]++;
 
    int twice = -1;
    rep(i, 1, N + 1) if (cnt[i] == 2) twice = i;
 
    int a = -1, b;
    rep(i, 0, N + 1) if (A[i] == twice) {
        if(a < 0) a = i;
        else b = i;
    }
 
    printf("%d\n", N);
    int cnt = a + (N - b);
    rep(i, 2, N + 1) {
        mint ans = com.aCb(N + 1, i);
        if(i - 1 <= cnt) ans -= com.aCb(cnt, i - 1);
        printf("%d\n", ans.get());
    }
    printf("1\n");
}