Pythonで数値リストに対する全クエリのkpr_sum(XOR総和)を効率的に求めるプログラム

数値のリスト nums と、複数のクエリを含むリストが与えられるとします。各クエリ queries[i] は [k, p, r] という3つの要素から構成され、それぞれのクエリに対して kpr_sum を計算する必要があります。

kpr_sum は次の数式で定義されます。

$$\mathrm{kpr\_sum} = \sum_{i=P}^{R-1}\sum_{j=i+1}^{R}\left(K \oplus (A[i] \oplus A[j])\right)$$

計算結果が非常に大きな値になる場合は、10⁹+7 で割った余り(モジュロ)を返します。

入力例と出力例

たとえば、入力が nums = [1,2,3]、queries = [[1,1,3],[2,1,3]] の場合、出力は [5, 4] になります。最初のクエリでは、(1 XOR (1 XOR 2)) + (1 XOR (1 XOR 3)) + (1 XOR (2 XOR 3)) = 5 となり、2番目のクエリについても同様の計算を行うと 4 になるためです。

解決手順

この問題を解くために、以下の手順に従います。

• m := 10⁹ + 7(剰余演算の基数)
• N := nums のサイズ
• q_cnt := queries のサイズ
• C := 新しいリスト(ビットごとの累積和を保持)
• res := 新しいリスト(各クエリの結果を保持)
• i を 0 から 19 まで繰り返す:
  • R := 初期要素 0 のみを持つ配列
  • t := 0
  • nums 内の各要素 x について:
    • t := t + ((x を i ビット右シフトした値) AND 1)
    • t を R の末尾に追加
  • R を C の末尾に追加
• j を 0 から q_cnt - 1 まで繰り返す:
  • (K, P, R) := queries[j]
  • d := R - P + 1(対象区間の長さ)
  • t := 0
  • i を 0 から 19 まで繰り返す:
    • n1 := C[i][R] - C[i][P-1](区間内で i ビット目が 1 の要素数)
    • n0 := d - n1(区間内で i ビット目が 0 の要素数)
    • (K を i ビット右シフトした値) AND 1 が 0 以外の場合:
      • x := (n1 × (n1 - 1) + n0 × (n0 - 1)) ÷ 2 の商
    • それ以外の場合:
      • x := n1 × n0
    • t := (t + (x を i ビット左シフトした値)) mod m
  • t を res の末尾に追加
• res を返す

アルゴリズムの考え方

このアプローチのポイントは、XOR 演算をビット単位に分解して考えることです。各ビット位置 i について累積和を利用すれば、任意の区間 [P, R] 内にある「i ビット目が 1 の要素の個数(n1)」と「i ビット目が 0 の要素の個数(n0)」を即座に取得できます。

K の i ビット目が 1 の場合、A[i] XOR A[j] の i ビット目が 0 になるペア(同じビット値を持つペア)のみが合計に寄与します。そのようなペアの数は、n1 から2つ選ぶ組み合わせと n0 から2つ選ぶ組み合わせの合計、すなわち (n1 × (n1 - 1) + n0 × (n0 - 1)) ÷ 2 です。一方、K の i ビット目が 0 の場合は、ビットが異なるペア n1 × n0 が寄与します。

これにより、各クエリを最大20ビット分のループだけで処理でき、前処理の計算量は O(20N)、各クエリの処理は O(20) となります。そのため、クエリの数が多くても高速に答えを求められるのが大きな利点です。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(nums, queries):
    m = 10**9 + 7
    N = len(nums)
    q_cnt = len(queries)
    C = []
    res = []
    for i in range(20):
        R = [0]
        t = 0
        for x in nums:
            t += (x >> i) & 1
            R.append(t)
        C.append(R)
    for j in range(q_cnt):
        K, P, R = queries[j]
        d = R - P + 1
        t = 0
        for i in range(20):
            n1 = C[i][R] - C[i][P-1]
            n0 = d - n1
            if (K >> i) & 1:
                x = (n1 * (n1 - 1) + n0 * (n0 - 1)) >> 1
            else:
                x = n1 * n0
            t = (t + (x << i)) % m
        res.append(t)

    return res

nums = [1,2,3]
queries = [[1,1,3],[2,1,3]]
print(solve(nums, queries))

入力

[1,2,3], [[1,1,3],[2,1,3]]

出力

[5, 4]