cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: cp_library/math/conv/and_conv_fast_fn.py

Depends on

Verified with

Code

import cp_library.__header__
import cp_library.math.__header__
import cp_library.math.conv.__header__
from cp_library.math.conv.superset_zeta_pair_fn import superset_zeta_pair
from cp_library.math.conv.superset_mobius_fn import superset_mobius

def and_conv(A: list[int], B: list[int], N: int, mod) -> list[int]:
    assert len(A) == len(B)
    Z = 1 << N
    superset_zeta_pair(A, B, N)
    for i, b in enumerate(B): A[i] = A[i]*b%mod
    superset_mobius(A, N)
    for i in range(Z): A[i] %= 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 superset_zeta_pair(A: list[int], B: list[int], N: int):
    Z = len(A)
    for i in range(N):
        m = b = 1<<i
        while m < Z:
            A[m ^ b] += A[m]
            B[m ^ b] += B[m]
            m = m+1|b
    return A

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

def and_conv(A: list[int], B: list[int], N: int, mod) -> list[int]:
    assert len(A) == len(B)
    Z = 1 << N
    superset_zeta_pair(A, B, N)
    for i, b in enumerate(B): A[i] = A[i]*b%mod
    superset_mobius(A, N)
    for i in range(Z): A[i] %= mod
    return A
Back to top page