parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 数え上げ 文字列 sに含まれる文字xの数をn(x)とする。c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。i>min(n(a), n(b))のときaまたはbの数が足りないからf[i] = 0i<=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)… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F05%2F03%2F120001" title="Counting Perfect Subsequences | HourRank 20 - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-05-03 12:00:01 rich https://par.hateblo.jp/entry/2017/05/03/120001 1.0 100%