こういうO(1)で気合導出、みたいな問題はめちゃくちゃ苦手…
解法
早い話、ありうる部分列を列挙して重複を除去すれば答えが出る。制約が大きいので重複の仕方が爆発してダメそうに見えるが、重複している数字が1個しかないので、重複の仕方を上手く見つけて場合分けすれば計算できる。
重複している数字をと置いて
で数列
を区切り、それぞれ左から区間を
とする。
それぞれの区間から1個も使わないときと1個以上使うときをに対応させると、
の4つの組が重複していることに気づける。
なので、それぞれのに対して
から以上4つの場合の数を引けば答えが出る。
については、
のときにだけ
を引けばよい。
については、
からそれぞれ
個を選ぶ数(1個は
のために予約している)なので、それぞれ
となる。
については、
双方から最低でも1個ずつ選んだうえで合計
個選ぶ数なので、
から、
片方からだけ
個選んでしまう数を引けばよく、結局、
となる。
以上から、のときは、
、それ以外のときは
が答えとなる。
時間計算量については、二項係数が階乗、逆元の階乗の前計算によってで求まるので、全体として
となる。
実装例は以下。
