Pythonの特定の数値リストに対するすべてのクエリのkpr合計を見つけるプログラム

numsの数のリストがあるとします。また、querys [i]に3つの要素[k、p、r]が含まれているクエリのリストもあります。クエリごとに、kpr_sumを見つける必要があります。 kpr_sumの式は次のようになります。

$$ \mathrm{{𝑘𝑝𝑟}\_{𝑠𝑢𝑚}=\ sum _ {\substack{𝑖=𝑃}}^{𝑅−1} \ sum _ {\substack{𝑗=𝑖+1}}^ {𝑅}（𝐾 ⊕（𝐴[𝑖]⊕𝐴[𝑗]））} $$

合計が大きすぎる場合は、10 ^ 9+7を法とする合計を返します。

したがって、入力がnums =[1,2,3]クエリ=[[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 ^ 9 + 7
• N：=numsのサイズ
• q_cnt：=クエリのサイズ
• C：=新しいリスト
• res：=新しいリスト
• 0〜19の範囲のiについては、
  • R：=単一要素0の配列
  • t：=0
  • numsのxごとに、
    • t：=t +（i回右にシフトした後のx）AND 1
    • Rの最後にtを挿入
  • Cの最後にRを挿入
• 0からq_cntの範囲のjについては、
  • （K、P、R）：=クエリ[j]
  • d：=R-P + 1
  • t：=0
  • 0〜19の範囲のiについては、
    • n1：=C [i、R]-C [i、P-1]
    • n0：=d --n1
    • （i回右にシフトした後のK）AND 1がゼロ以外の場合、
      • x：=（n1 *（n1 --1）+ n0 *（n0 -1））/2の商
    • それ以外の場合、
      • x：=n1 * n0
    • t：=（t +（i回左にシフトした後のx））mod m
  • resの最後にtを挿入
• return res

例

理解を深めるために、次の実装を見てみましょう-

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]