ABC150 - E - Change a Little Bit - Senの競技プログラミング備忘録

概要

長さNの相異なるバイナリ列、S, Tを考える。C[]という長さNの配列が与えられる。Sのi(1-idx)桁目を変更するとき、C[i]*(変更直前のS xor Tの立ってるbit数)だけのコストがかかる。次のようにf(S, T)を定める。

SをTと一致させるときにかかる最低コスト。

長さNの相異なるすべてのSとTについて、f(S, T)を計算しこれらの総和を10^9+7で割ったあまりを求めよ。

制約： 1 <= N <= 10^5, 1 <= C[i] <= 10^9

ACするまで

1. すべてを数え上げよ、タイプの問題なので、それぞれのC[i]の数えられた回数に着目する。
2. SとTがあるとき、f(S, T)に当たる操作は、そもそも変更すべきか所のうち、Cが高い場所から変更することである。また、す、Cを昇順にソートしても、一般性を失わないので、ソートする。理由は考察で。
3. 丁寧にモデリングしていくと、数式が出てくる。これを愚直に計算すると、O(N^2)となって、TLEする。
4. 数学的な式変形を行う。受験数学でおなじみだったはずの等式を使って、次元を1つおとしてO(N) -> AC

考察

以下の考察はのCのインデックスは0-idxとする。

f(S, T)はコストの高いところから操作していくことで得られるので、Cが大きい桁から操作する、から考える。Cの各要素がそれぞれ何回総和に寄与するか？を考えるとき、必要なのは今着目してるC[i]はCの中で何番目なのか、という情報なので、いくらC[]の順序をソートしても一般性を失わない。ここでは昇順にソートする。

C[0]の寄与する値を考えてみる。
ここでは、まずC[0]がf(S, T)を求める過程で足される回数を考える。

0回。この時、SとTは「C[0]の桁がそもそも一致してる」
1回。この時、SとTは「C[0]の桁が違う上で、C[1~N - 1]の桁はすべて一致する」
2回。この時、SとTは「C[0]の桁が違う上で、C[1~N - 1]の桁は1つだけ違う」

これを一般化すると、

k回(k >= 1)。SとTは「C[0]の桁が違う上で、C[1~N - 1]の桁はk - 1つだけ違う」

それぞれが寄与する回数を考える。

0回。この時、もちろん0通り。
1回。異なる桁の選び方は1通り(C[0]のみ)。この時、C[0]は1回足される。SとTは、一致する桁でも異なる桁でも、(0, 0)と(1, 1)、(1, 0)と(0, 1)という2通りの表し方があるため、全体で、2^N通りまたかかる。
2回。異なる桁の選び方は $_{N-1} C _1$ 通り(C[0]+C[1~N - 1]のうちから1つ)。この時、C[0]は2回足される。また同じ理由で全体で、2^N通りまたかかる。

一般化すると、

k(k <= N - 1)回。異なる桁の選び方は $_{N-1} \mathrm{C} _{k-1}$ 通り(C[0]+C[1~N - 1]のうちからk - 1つ)。この時、C[0]はk回足される。また同じ理由で全体で、2^N通りまたかかる。

C[0]だけではなく、ほかのC[i](i >= 1)の場合では、数えられる回数として

k回(k >= 1)。SとTは「C[i]の桁が違う上で、C[i+1~N - 1]の桁はk - 1つだけ違う」ここで、SとTのC[0 ~ k - 1]の桁は、被っていようが被っていまいが同じようにk回数えられるので、全部数え上げの対象になる。(C[i]が数え上げられるのは、C[i + 1 ~ N - 1]にある変更が必要な個数にのみ依存する)このことから、2^i通りまた、バリエーションが増える。

このことを踏まえると、C[i]がk回数え上げられるパターンが寄与する量は、

k(k <= N - 1)回。異なる桁の選び方は $_{N-1} C _{k-1}$ 通り(C[0]+C[1~N - 1]のうちからk - 1つ)。この時、C[0]はk回足される。そして、C[0 ~ i - 1]の間は重複してようがしてまいが全部対称なので、2^i通りまた増える。その上、全体で、2^N通りまたかかる。

さて、ここまでで考察は詰め終わった。答えを数式に直すと、
$2^N \sum_{i=0}^{N - 1} C_i(2^i (\sum_{j=0}^{j=N-1-i} (i+1) _{N - 1 - i} \mathrm{C} _{j}))$
上の式は $C$ が配列とコンビネーションの演算子の両方に使われてることを注意してください。