cp_library/math/conv/mod/ixor_conv_fn.py

View this file on GitHub
Last update: 2025-03-30 20:17:47+09:00

Depends on

Required by

cp_library/math/conv/mod/xor_conv_fn.py

Verified with

test/library-checker/convolution/bitwise_xor_convolution.test.py

Code

import cp_library.__header__
import cp_library.math.__header__
import cp_library.math.conv.__header__
import cp_library.math.conv.mod.__header__
from cp_library.math.conv.mod.fwht_inv_fn import fwht_inv
from cp_library.math.conv.fwht_pair_fn import fwht_pair

def ixor_conv(A: list[int], B: list[int], N: int, mod: int) -> list[int]:
    assert len(A) == len(B)
    fwht_pair(A, B, N)
    for i, b in enumerate(B): A[i] = A[i]%mod * (b%mod) % mod
    fwht_inv(A, N, mod)
    return A

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
    x₀ ────────●─●────────●───●────────●───────●────────► X₀
                ╳          ╲ ╱          ╲     ╱          
    x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
                           ╳ ╳          ╲ ╲ ╱ ╱          
    x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
                ╳          ╱ ╲          ╲ ╳ ╳ ╱          
    x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
                                        ╳ ╳ ╳ ╳         
    x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
                ╳          ╲ ╱          ╱ ╳ ╳ ╲          
    x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
                           ╳ ╳          ╱ ╱ ╲ ╲          
    x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
                ╳          ╱ ╲          ╱     ╲          
    x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
                      Math - Convolution                     
'''


def fwht(A: list, N: int):
    Z = len(A)
    for i in range(N):
        m = b = 1<<i
        while m < Z:
            a0, a1 = A[m^b], A[m]
            A[m^b], A[m] = a0+a1, a0-a1
            m = m+1|b
    return A

def fwht_inv(A: list[int], N: int, mod: int) -> list[int]:
    fwht(A, N)
    inv = pow(1 << N, -1, mod)
    for i, a in enumerate(A): A[i] = a%mod * inv%mod
    return A

def fwht_pair(A: list[int], B: list[int], N: int):
    Z = len(A)
    for i in range(N):
        m = b = 1<<i
        while m < Z:
            a0, a1, b0, b1 = A[m^b], A[m], B[m^b], B[m]
            A[m^b], A[m], B[m^b], B[m] = a0+a1, a0-a1, b0+b1, b0-b1
            m = m+1|b
    return A, B

def ixor_conv(A: list[int], B: list[int], N: int, mod: int) -> list[int]:
    assert len(A) == len(B)
    fwht_pair(A, B, N)
    for i, b in enumerate(B): A[i] = A[i]%mod * (b%mod) % mod
    fwht_inv(A, N, mod)
    return A