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); } } }
ポイント
- 何に着目して数え上げるか