D - 11
個の数列の中で1組のみ等しいものがあり, それ以外は互いに異なる要素であることがポイントです.
問題を少し簡単にして, この等しいもの2つの中から１つのみを取り除いて
個の数列について, k個の部分列の個数を考えてみます. この数列において要素はそれぞれ異なっているため, k個の部分列の個数はこの要素の中からk個取り出す場合の数と一致します. よってこのときの答えは
となります.
もとの問題に戻り, この数列に対しても
を考えてみましょう. このとき, この組み合わせの数には重複が存在します. なぜならば, 等しい要素が存在しているために全く同じ数列を複数回カウントしてしまうからです.
の組み合わせの中から重複しているものを取り除く方法について考察します. そもそも, 重複するような組み合わせはどのようなものでしょうか.
等しい組の左の方を
, 右の方を
とします. 重複して数えてしまう組み合わせは, このどちらかを含んでいます . 重複して数えてしまうものは, このとの数列上の順番に対し, どちらの数字の場所を選んでも成立するようなものです.
具体的に言うと, の左側の数列との右側の数列から
個を選ぶとき, 数列内の等しい組のまたはのどちらかを選んで加えることができます. このような要素が重複となっているので, これを一回分引いてあげれば答えです.
との中間の要素を含む部分列が存在すると, とのどちらの要素を使っているかが特定できるので重複にはなりません.
実装には
逆元ライブラリを用いました. パスカルの三角形で組み合わせを求める方法だと空間も足りず, 時間も間に合いません.
Submission #2979027 - AtCoder Beginner Contest 066
