Counting Perfect Subsequences | HourRank 20

sに含まれる文字xの数をn(x)とする。
c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。
f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。
i>min(n(a), n(b))のとき
aまたはbの数が足りないから
f[i] = 0
i<=min(n(a), n(b))のとき
n(a)個のaのうちi個の選び方はC(n(a), i)
n(b)個のbのうちi個の選び方はC(n(b), i)
よって
f[i] = C(n(a), i)*C(n(b), i)

同様にc, dだけを考えてg[j]をc, dをちょうどi個含む部分列の数とすれば
g[j] = C(n(c), j)*C(n(d), j)

あとは、空の部分列になる(0, 0)以外のすべての(i, j)の組について考えれば良いので
ans
= Σ(f[i]g[j])-1
= Σ(f[i]) * Σ(g[i]) - 1
で求まった。

この数式変形はよくある。例えば、
1*4+1*5+1*6 + 2*4+2*5+2*6 + 3*4+3*5+3*6
= (1+2+3)*(4+5+6)

広告を非表示にする