競技プログラミング用 知識集積所
ABC429C - Odd One Subsequence
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
組み合わせの基本問題。
条件を満たすパターンを漏れなくダブりなくグループ分けして、それぞれの個数を合計する。
つまり、Aに含まれる全ての種類の数について、「それを2個、別のを1個」選ぶパターンを数えればよい。
問題にはi<j<kという指定があるが、3つ選んだあとでどれをiにするかなど割り当てればよいので、この大小指定は選び方の数に影響しない。
条件を満たすパターンを漏れなくダブりなくグループ分けして、それぞれの個数を合計する。
つまり、Aに含まれる全ての種類の数について、「それを2個、別のを1個」選ぶパターンを数えればよい。
問題にはi<j<kという指定があるが、3つ選んだあとでどれをiにするかなど割り当てればよいので、この大小指定は選び方の数に影響しない。
例えば入力例1の場合。
2を2個選ぶパターンは二項係数※を使ってcomb(3,2)=3通り。
そこに違う数を選ぶパターンは、2以外の数の個数なので、5-3=2通り。
これらを掛け合わせて6通り。
3を2個選んだり、5を2個選んだりするパターンは存在しない。
よって6+0+0で合計6通り。
……という感じ。
2を2個選ぶパターンは二項係数※を使ってcomb(3,2)=3通り。
そこに違う数を選ぶパターンは、2以外の数の個数なので、5-3=2通り。
これらを掛け合わせて6通り。
3を2個選んだり、5を2個選んだりするパターンは存在しない。
よって6+0+0で合計6通り。
……という感じ。
二項係数※は、rが2なので愚直に計算してしまってよい。
解答例
注意点
long long型を使用する
Nが20万で、1と2が10万個ずつある場合、答えは約10^15になる。
int型には入りきらないので注意。
int型には入りきらないので注意。
