ABC066-D:11(600)

問題

https://beta.atcoder.jp/contests/abc066/tasks/arc077_b

考え方

同じ数で場合分けする。同じ数を左から a_l, a_r とする。

k 個選ぶときの選び方について考える。

(i)同じ数を0個選ぶ場合
n-1 個の数から k 個選ぶ場合の場合の数

n-1 C k

(ii)同じ数を2個選ぶ場合
n-1 個の数から k-2 個選ぶ場合の場合の数

n-1 C k-2

(iii)同じ数を1個選ぶ場合

(A) 少なくとも [l, r] からひとつ以上の数を選択するとき
この場合は a_l, a_r を選んだ場合で別の部分列になる。これは同じ数を 1 つ選んだときの組み合わせから、ひとつも [l, r] から選ばずに部分列を選んだときの組み合わせの数を引けばいい。 a_l, a_r の選び方は 2 通りあるので、全体の組み合わせとしては 2 * ( n-1 C k-1 - l+n-r C k-1 ) となる。

(B) すべて [1, l) (r, n+1] から選択するとき この場合は a_l, a_r をひとつ選んだときに同じ部分列が選ばれる。よって組み合わせは l+n-r C k-1 である。

(A), (B) をあわせて 2 * ( n-1 C k-1 - l-1+n-r C k-1 ) + l-1+n-r C k-1 = 2 * n-1 C k-1 - l+n-r C k-1 となる。

よって k 個選ぶときの部分列の個数は

n-1 C k + n-1 C k-2 + 2 * n-1 C k-1 - l+n-r C k-1

となる。

よって、答えは k を [1, n+1] 分求めれば良い。

public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] a = in.nextIntArray(n+1);

            int l = INF, r = -INF, num = -1;
            Set<Integer> set = new HashSet<>();
            for (int i : a) {
                if (set.contains(i)) {
                    num = i;
                    break;
                } else {
                    set.add(i);
                }
            }

            for (int i = 0; i < n+1; i++) {
                if (a[i] == num) {
                    l = Math.min(l, i);
                    r = Math.max(r, i);
                }
            }

            for (int k = 1; k <= n+1; k++) {

                long ans = 0;

                if (k == 1) {
                    out.println(n);
                    continue;
                }

                ans += comb(n-1, k);
                ans += comb(n-1, k-2);
                ans += 2 * comb(n-1, k-1) - comb(l+n-r, k-1);

                out.println(ans % MOD);

            }

        }
    }

ポイント

  • 何に着目して数え上げるか