問題文は以下のリンクから。
atcoder.jp
(((((考察アホほど違ってた))))))))))
AtCoder Beginner Contest151 のE問題 Max-Min Sumsとだいぶ似ている問題。
この問題についても
はソートしておいて大丈夫。
が何回足されるかに注目する。
に着目する。より大きいコストを持つビットについては考察にいれなくて良い。（それらのビットが異なっていようと、同じであろうとどちらでも良い）。今考えているのはコストの和の最小値である。自分よりコストが大きいビットに関しては先に処理する。が操作されずに残っている時、他に残っているのはよりコストが小さいビットのみである。
よってよりコストが大きいビットに関して、ST間で「同じ」か「異なる」か２通りありビット数はn-k個あるので
通り考えられる。
問題になるのは、よりコストが小さいビットに関してである。そのビットの数はk-1個あるわけだが、そのビットに関してST間で「同じ」か「異なる」かを考える。j個異なると考えると、k-1個の中からj個を選ぶ組み合わせが
通りである。そして、前に残っているj個より先にを操作する必要があり、そのコストは
である。それを考慮すると以下の和を求める必要が出てくる。
これに先ほどのをかける。これを0~N-1で和をとってやればおk。
だが問題の上の和をどのようにして求めるかがなかなか謎だ。
どうすれば良いのかわかったら追記する。
追記
