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

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00
• Problem: https://judge.yosupo.jp/problem/bitwise_and_convolution

Depends on

• cp_library/io/fast/fast_io_fn.py
• cp_library/math/conv/and_conv_fast_fn.py
• cp_library/math/conv/superset_mobius_fn.py
• cp_library/math/conv/superset_zeta_pair_fn.py

Code

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/bitwise_and_convolution

def main():
    N = rd()
    A = rdl(1 << N)
    B = rdl(1 << N)
    wtnl(and_conv(A, B, N, 998244353))

from cp_library.math.conv.and_conv_fast_fn import and_conv
from cp_library.io.fast.fast_io_fn import rd, rdl, wtnl

if __name__ == '__main__':
    main()

# verification-helper: PROBLEM https://judge.yosupo.jp/problem/bitwise_and_convolution

def main():
    N = rd()
    A = rdl(1 << N)
    B = rdl(1 << N)
    wtnl(and_conv(A, B, N, 998244353))

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             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
from __pypy__.builders import StringBuilder
import sys
from os import read as os_read, write as os_write
from atexit import register as atexist_register

class Fastio:
    ibuf = bytes()
    pil = pir = 0
    sb = StringBuilder()
    def load(self):
        self.ibuf = self.ibuf[self.pil:]
        self.ibuf += os_read(0, 131072)
        self.pil = 0; self.pir = len(self.ibuf)
    def flush_atexit(self): os_write(1, self.sb.build().encode())
    def flush(self):
        os_write(1, self.sb.build().encode())
        self.sb = StringBuilder()
    def fastin(self):
        if self.pir - self.pil < 64: self.load()
        minus = x = 0
        while self.ibuf[self.pil] < 45: self.pil += 1
        if self.ibuf[self.pil] == 45: minus = 1; self.pil += 1
        while self.ibuf[self.pil] >= 48:
            x = x * 10 + (self.ibuf[self.pil] & 15)
            self.pil += 1
        if minus: return -x
        return x
    def fastin_string(self):
        if self.pir - self.pil < 64: self.load()
        while self.ibuf[self.pil] <= 32: self.pil += 1
        res = bytearray()
        while self.ibuf[self.pil] > 32:
            if self.pir - self.pil < 64: self.load()
            res.append(self.ibuf[self.pil])
            self.pil += 1
        return res
    def fastout(self, x): self.sb.append(str(x))
    def fastoutln(self, x): self.sb.append(str(x)); self.sb.append('\n')
fastio = Fastio()
rd = fastio.fastin; rds = fastio.fastin_string; wt = fastio.fastout; wtn = fastio.fastoutln; flush = fastio.flush
atexist_register(fastio.flush_atexit)
sys.stdin = None; sys.stdout = None
def rdl(n): return [rd() for _ in range(n)]
def wtnl(l): wtn(' '.join(map(str, l)))

if __name__ == '__main__':
    main()

Back to top page