cp_library/math/conv/iand_conv_ring_fn.py

View this file on GitHub
Last update: 2025-08-24 20:27:05+09:00

Depends on

cp_library/math/conv/iand_transform_fn.py

Verified with

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

Code

import cp_library.__header__
import operator
from typing import Callable
from cp_library.misc.typing import _T
import cp_library.math.__header__
import cp_library.math.conv.__header__
from cp_library.math.conv.iand_transform_fn import iand_transform

def iand_conv_ring(A: list[_T], B: list[_T], N: int,
             mul: Callable[[_T,_T],_T] = operator.mul,
             sub: Callable[[_T,_T],_T] = operator.sub,
             add: Callable[[_T,_T],_T] = operator.add) -> list[_T]:
    assert len(A) == len(B)
    iand_transform(A, N, op=add), iand_transform(B, N, op=add)
    for i, b in enumerate(B): A[i] = mul(A[i], b)
    return iand_transform(A, N, op=sub)

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
import operator
from typing import Callable
from typing import TypeVar

_S = TypeVar('S'); _T = TypeVar('T'); _U = TypeVar('U'); _T1 = TypeVar('T1'); _T2 = TypeVar('T2'); _T3 = TypeVar('T3'); _T4 = TypeVar('T4'); _T5 = TypeVar('T5'); _T6 = TypeVar('T6')

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

def iand_transform(A: list[_T], N: int, /, op = operator.add) -> list[_T]:
    Z = len(A)
    for i in range(N):
        m = b = 1<<i
        while m < Z: A[m^b], m = op(A[m^b], A[m]), m+1|b
    return A

def iand_conv_ring(A: list[_T], B: list[_T], N: int,
             mul: Callable[[_T,_T],_T] = operator.mul,
             sub: Callable[[_T,_T],_T] = operator.sub,
             add: Callable[[_T,_T],_T] = operator.add) -> list[_T]:
    assert len(A) == len(B)
    iand_transform(A, N, op=add), iand_transform(B, N, op=add)
    for i, b in enumerate(B): A[i] = mul(A[i], b)
    return iand_transform(A, N, op=sub)