cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/library-checker/set-power-series/subset_convolution_all.test.py
- View this file on GitHub
- Last update: 2025-08-24 20:27:05+09:00
- Problem: https://judge.yosupo.jp/problem/subset_convolution
Depends on
- cp_library/alg/dp/max2_fn.py
- cp_library/bit/popcnts_fn.py
- cp_library/io/io_base_cls.py
- cp_library/io/io_cls.py
- cp_library/io/parsable_cls.py
- cp_library/io/parser_cls.py
- cp_library/io/read_fn.py
- cp_library/io/write_fn.py
- cp_library/math/conv/ior_mobius_ranked_fn.py
- cp_library/math/conv/ior_zeta_pair_ranked_fn.py
- cp_library/math/conv/isubset_conv_ranked_fn.py
- cp_library/math/conv/isubset_deconv_ranked_fn.py
- cp_library/math/conv/mod/isubset_conv_ranked_fn.py
- cp_library/math/conv/mod/isubset_deconv_ranked_fn.py
- cp_library/math/conv/mod/subset_conv_fn.py
- cp_library/math/conv/mod/subset_deconv_fn.py
- cp_library/math/conv/subset_conv_fn.py
- cp_library/math/conv/subset_deconv_fn.py
- cp_library/math/mod/mint_cls.py
Code
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/subset_convolution
from cp_library.io.read_fn import read
from cp_library.io.write_fn import write
mod = 998244353
N, = read()
if N < 10:
from cp_library.math.conv.subset_conv_fn import subset_conv
from cp_library.math.conv.subset_deconv_fn import subset_deconv
from cp_library.math.mod.mint_cls import mint
mint.set_mod(mod)
F = read(list[mint])
G = read(list[mint])
H = subset_conv(F, G, N)
write(*H)
assert subset_deconv(H, G, N) == F
else:
from cp_library.math.conv.mod.subset_conv_fn import subset_conv
from cp_library.math.conv.mod.subset_deconv_fn import subset_deconv
F = read(list[int])
G = read(list[int])
H = subset_conv(F, G, N, mod)
write(*H)
assert subset_deconv(H, G, N, mod) == F# verification-helper: PROBLEM https://judge.yosupo.jp/problem/subset_convolution
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
from typing import Type, Union, overload
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')
@overload
def read() -> list[int]: ...
@overload
def read(spec: Type[_T], char=False) -> _T: ...
@overload
def read(spec: _U, char=False) -> _U: ...
@overload
def read(*specs: Type[_T], char=False) -> tuple[_T, ...]: ...
@overload
def read(*specs: _U, char=False) -> tuple[_U, ...]: ...
def read(*specs: Union[Type[_T],_T], char=False):
IO.stdin.char = char
if not specs: return IO.stdin.readnumsinto([])
parser: _T = Parser.compile(specs[0] if len(specs) == 1 else specs)
return parser(IO.stdin)
from os import read as os_read, write as os_write, fstat as os_fstat
import sys
from __pypy__.builders import StringBuilder
def max2(a, b): return a if a > b else b
class IOBase:
@property
def char(io) -> bool: ...
@property
def writable(io) -> bool: ...
def __next__(io) -> str: ...
def write(io, s: str) -> None: ...
def readline(io) -> str: ...
def readtoken(io) -> str: ...
def readtokens(io) -> list[str]: ...
def readints(io) -> list[int]: ...
def readdigits(io) -> list[int]: ...
def readnums(io) -> list[int]: ...
def readchar(io) -> str: ...
def readchars(io) -> str: ...
def readinto(io, lst: list[str]) -> list[str]: ...
def readcharsinto(io, lst: list[str]) -> list[str]: ...
def readtokensinto(io, lst: list[str]) -> list[str]: ...
def readintsinto(io, lst: list[int]) -> list[int]: ...
def readdigitsinto(io, lst: list[int]) -> list[int]: ...
def readnumsinto(io, lst: list[int]) -> list[int]: ...
def wait(io): ...
def flush(io) -> None: ...
def line(io) -> list[str]: ...
class IO(IOBase):
BUFSIZE = 1 << 16; stdin: 'IO'; stdout: 'IO'
__slots__ = 'f', 'file', 'B', 'O', 'V', 'S', 'l', 'p', 'char', 'sz', 'st', 'ist', 'writable', 'encoding', 'errors'
def __init__(io, file):
io.file = file
try: io.f = file.fileno(); io.sz, io.writable = max2(io.BUFSIZE, os_fstat(io.f).st_size), ('x' in file.mode or 'r' not in file.mode)
except: io.f, io.sz, io.writable = -1, io.BUFSIZE, False
io.B, io.O, io.S = bytearray(), [], StringBuilder(); io.V = memoryview(io.B); io.l = io.p = 0
io.char, io.st, io.ist, io.encoding, io.errors = False, [], [], 'ascii', 'ignore'
def _dec(io, l, r): return io.V[l:r].tobytes().decode(io.encoding, io.errors)
def readbytes(io, sz): return os_read(io.f, sz)
def load(io):
while io.l >= len(io.O):
if not (b := io.readbytes(io.sz)):
if io.O[-1] < len(io.B): io.O.append(len(io.B))
break
pos = len(io.B); io.B.extend(b)
while ~(pos := io.B.find(b'\n', pos)): io.O.append(pos := pos+1)
def __next__(io):
if io.char: return io.readchar()
else: return io.readtoken()
def readchar(io):
io.load(); r = io.O[io.l]
c = chr(io.B[io.p])
if io.p >= r-1: io.p = r; io.l += 1
else: io.p += 1
return c
def write(io, s: str): io.S.append(s)
def readline(io): io.load(); l, io.p = io.p, io.O[io.l]; io.l += 1; return io._dec(l, io.p)
def readtoken(io):
io.load(); r = io.O[io.l]
if ~(p := io.B.find(b' ', io.p, r)): s = io._dec(io.p, p); io.p = p+1
else: s = io._dec(io.p, r-1); io.p = r; io.l += 1
return s
def readtokens(io): io.st.clear(); return io.readtokensinto(io.st)
def readints(io): io.ist.clear(); return io.readintsinto(io.ist)
def readdigits(io): io.ist.clear(); return io.readdigitsinto(io.ist)
def readnums(io): io.ist.clear(); return io.readnumsinto(io.ist)
def readchars(io): io.load(); l, io.p = io.p, io.O[io.l]; io.l += 1; return io._dec(l, io.p-1)
def readinto(io, lst):
if io.char: return io.readcharsinto(lst)
else: return io.readtokensinto(lst)
def readcharsinto(io, lst): lst.extend(io.readchars()); return lst
def readtokensinto(io, lst):
io.load(); r = io.O[io.l]
while ~(p := io.B.find(b' ', io.p, r)): lst.append(io._dec(io.p, p)); io.p = p+1
lst.append(io._dec(io.p, r-1)); io.p = r; io.l += 1; return lst
def _readint(io, r):
while io.p < r and io.B[io.p] <= 32: io.p += 1
if io.p >= r: return None
minus = x = 0
if io.B[io.p] == 45: minus = 1; io.p += 1
while io.p < r and io.B[io.p] >= 48: x = x * 10 + (io.B[io.p] & 15); io.p += 1
io.p += 1
return -x if minus else x
def readintsinto(io, lst):
io.load(); r = io.O[io.l]
while io.p < r and (x := io._readint(r)) is not None: lst.append(x)
io.l += 1; return lst
def _readdigit(io): d = io.B[io.p] & 15; io.p += 1; return d
def readdigitsinto(io, lst):
io.load(); r = io.O[io.l]
while io.p < r and io.B[io.p] > 32: lst.append(io._readdigit())
if io.B[io.p] == 10: io.l += 1
io.p += 1
return lst
def readnumsinto(io, lst):
if io.char: return io.readdigitsinto(lst)
else: return io.readintsinto(lst)
def line(io): io.st.clear(); return io.readinto(io.st)
def wait(io):
io.load(); r = io.O[io.l]
while io.p < r: yield
def flush(io):
if io.writable: os_write(io.f, io.S.build().encode(io.encoding, io.errors)); io.S = StringBuilder()
sys.stdin = IO.stdin = IO(sys.stdin); sys.stdout = IO.stdout = IO(sys.stdout)
import typing
from numbers import Number
from types import GenericAlias
from typing import Callable, Collection
class Parsable:
@classmethod
def compile(cls):
def parser(io: 'IOBase'): return cls(next(io))
return parser
@classmethod
def __class_getitem__(cls, item): return GenericAlias(cls, item)
class Parser:
def __init__(self, spec): self.parse = Parser.compile(spec)
def __call__(self, io: IOBase): return self.parse(io)
@staticmethod
def compile_type(cls, args = ()):
if issubclass(cls, Parsable): return cls.compile(*args)
elif issubclass(cls, (Number, str)):
def parse(io: IOBase): return cls(next(io))
return parse
elif issubclass(cls, tuple): return Parser.compile_tuple(cls, args)
elif issubclass(cls, Collection): return Parser.compile_collection(cls, args)
elif callable(cls):
def parse(io: IOBase): return cls(next(io))
return parse
else: raise NotImplementedError()
@staticmethod
def compile(spec=int):
if isinstance(spec, (type, GenericAlias)):
cls, args = typing.get_origin(spec) or spec, typing.get_args(spec) or tuple()
return Parser.compile_type(cls, args)
elif isinstance(offset := spec, Number):
cls = type(spec)
def parse(io: IOBase): return cls(next(io)) + offset
return parse
elif isinstance(args := spec, tuple): return Parser.compile_tuple(type(spec), args)
elif isinstance(args := spec, Collection): return Parser.compile_collection(type(spec), args)
elif isinstance(fn := spec, Callable):
def parse(io: IOBase): return fn(next(io))
return parse
else: raise NotImplementedError()
@staticmethod
def compile_line(cls, spec=int):
if spec is int:
def parse(io: IOBase): return cls(io.readnums())
elif spec is str:
def parse(io: IOBase): return cls(io.line())
else:
fn = Parser.compile(spec)
def parse(io: IOBase): return cls((fn(io) for _ in io.wait()))
return parse
@staticmethod
def compile_repeat(cls, spec, N):
fn = Parser.compile(spec)
def parse(io: IOBase): return cls([fn(io) for _ in range(N)])
return parse
@staticmethod
def compile_children(cls, specs):
fns = tuple((Parser.compile(spec) for spec in specs))
def parse(io: IOBase): return cls([fn(io) for fn in fns])
return parse
@staticmethod
def compile_tuple(cls, specs):
if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...: return Parser.compile_line(cls, specs[0])
else: return Parser.compile_children(cls, specs)
@staticmethod
def compile_collection(cls, specs):
if not specs or len(specs) == 1 or isinstance(specs, set):
return Parser.compile_line(cls, *specs)
elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
return Parser.compile_repeat(cls, specs[0], specs[1])
else:
raise NotImplementedError()
def write(*args, **kwargs):
'''Prints the values to a stream, or to stdout_fast by default.'''
sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IO.stdout)
at_start = True
for x in args:
if not at_start: file.write(sep)
file.write(str(x))
at_start = False
file.write(kwargs.pop("end", "\n"))
if kwargs.pop("flush", False): file.flush()
mod = 998244353
N, = read()
if N < 10:
def popcnts(N):
P = [0]*(1 << N)
for i in range(N):
for m in range(b := 1<<i):
P[m^b] = P[m] + 1
return P
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_zeta_pair_ranked(A, B, N, M, Z):
for i in range(0, Z, M):
l, r = i+(1<<(i>>N))-1, i+M
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] += A[m^b]; B[m] += B[m^b]; m = m+1|b
return A, B
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_mobius_ranked(A: list[int], N: int, M: int, Z: int):
for i in range(0, Z, M):
l, r = i, i+M-(1<<(N-(i>>N)))+1
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] -= A[m^b]; m = m+1|b
return A
def isubset_conv_ranked(Ar, Br, N, M, Z) -> list[int]:
ior_zeta_pair_ranked(Ar, Br, N, M, Z)
for ij in range(Z-M,-1,-M):
for k in range(M): Ar[ij|k] *= Br[k]
r = M-(1 << (N-(ij>>N)))+1
for i in range(0,ij,M):
j = ij-i; l = (1 << (max2(i,j)>>N))-1
for k in range(l,r): Ar[ij|k] += Ar[i|k] * Br[j|k]
return ior_mobius_ranked(Ar, N, M, Z)
def subset_conv(A: list[int], B: list[int], N: int) -> list[int]:
Z = (N+1)*(M:=1<<N)
Ar, Br, P = [0]*Z, [0]*Z, popcnts(N)
for i, p in enumerate(P): Ar[p<<N|i], Br[p<<N|i] = A[i], B[i]
isubset_conv_ranked(Ar, Br, N, M, Z)
return [Ar[p<<N|i] for i, p in enumerate(P)]
def popcnts(N):
P = [0]*(1 << N)
for i in range(N):
for m in range(b := 1<<i):
P[m^b] = P[m] + 1
return P
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_zeta_pair_ranked(A, B, N, M, Z):
for i in range(0, Z, M):
l, r = i+(1<<(i>>N))-1, i+M
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] += A[m^b]; B[m] += B[m^b]; m = m+1|b
return A, B
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_mobius_ranked(A: list[int], N: int, M: int, Z: int):
for i in range(0, Z, M):
l, r = i, i+M-(1<<(N-(i>>N)))+1
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] -= A[m^b]; m = m+1|b
return A
def isubset_deconv_ranked(Ar, Br, N, Z, M):
inv = 1 // Br[0]; ior_zeta_pair_ranked(Ar, Br, N, M, Z)
for i in range(0, Z, M):
for k in range(M): Ar[i|k] *= inv
for j in range(M, Z-i, M):
ij = i + j; l = (1 << (j>>N))-1
for k in range(l, M): Ar[ij|k] -= Ar[i|k] * Br[j|k]
return ior_mobius_ranked(Ar, N, M, Z)
def subset_deconv(A: list[int], B: list[int], N: int) -> list[int]:
Z = (N+1)*(M:=1<<N)
Ar, Br, C, P = [0]*Z, [0]*Z, [0]*M, popcnts(N)
for i, p in enumerate(P): Ar[p<<N|i], Br[p<<N|i] = A[i], B[i]
isubset_deconv_ranked(Ar, Br, N, Z, M)
for i, p in enumerate(P): C[i] = Ar[p<<N|i]
return C
class mint(int):
mod: int
zero: 'mint'
one: 'mint'
two: 'mint'
cache: list['mint']
def __new__(cls, *args, **kwargs):
if 0 <= (x := int(*args, **kwargs)) < 64: return cls.cache[x]
else: return cls.fix(x)
@classmethod
def set_mod(cls, mod: int):
mint.mod = cls.mod = mod
mint.zero = cls.zero = cls.cast(0)
mint.one = cls.one = cls.fix(1)
mint.two = cls.two = cls.fix(2)
mint.cache = cls.cache = [cls.zero, cls.one, cls.two]
for x in range(3,64): mint.cache.append(cls.fix(x))
@classmethod
def fix(cls, x): return cls.cast(x%cls.mod)
@classmethod
def cast(cls, x): return super().__new__(cls,x)
@classmethod
def mod_inv(cls, x):
a,b,s,t = int(x), cls.mod, 1, 0
while b: a,b,s,t = b,a%b,t,s-a//b*t
if a == 1: return cls.fix(s)
raise ValueError(f"{x} is not invertible in mod {cls.mod}")
@property
def inv(self): return mint.mod_inv(self)
def __add__(self, x): return mint.fix(super().__add__(x))
def __radd__(self, x): return mint.fix(super().__radd__(x))
def __sub__(self, x): return mint.fix(super().__sub__(x))
def __rsub__(self, x): return mint.fix(super().__rsub__(x))
def __mul__(self, x): return mint.fix(super().__mul__(x))
def __rmul__(self, x): return mint.fix(super().__rmul__(x))
def __floordiv__(self, x): return self * mint.mod_inv(x)
def __rfloordiv__(self, x): return self.inv * x
def __truediv__(self, x): return self * mint.mod_inv(x)
def __rtruediv__(self, x): return self.inv * x
def __pow__(self, x): return self.cast(super().__pow__(x, self.mod))
def __neg__(self): return mint.mod-self
def __pos__(self): return self
def __abs__(self): return self
def __class_getitem__(self, x: int): return self.cache[x]
mint.set_mod(mod)
F = read(list[mint])
G = read(list[mint])
H = subset_conv(F, G, N)
write(*H)
assert subset_deconv(H, G, N) == F
else:
def popcnts(N):
P = [0]*(1 << N)
for i in range(N):
for m in range(b := 1<<i):
P[m^b] = P[m] + 1
return P
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_zeta_pair_ranked(A, B, N, M, Z):
for i in range(0, Z, M):
l, r = i+(1<<(i>>N))-1, i+M
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] += A[m^b]; B[m] += B[m^b]; m = m+1|b
return A, B
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_mobius_ranked(A: list[int], N: int, M: int, Z: int):
for i in range(0, Z, M):
l, r = i, i+M-(1<<(N-(i>>N)))+1
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] -= A[m^b]; m = m+1|b
return A
def isubset_conv_ranked(Ar, Br, N, M, Z, mod) -> list[int]:
ior_zeta_pair_ranked(Ar, Br, N, M, Z)
for i in range(Z): Ar[i], Br[i] = Ar[i]%mod, Br[i]%mod
for ij in range(Z-M,-1,-M):
for k in range(M): Ar[ij|k] = (Ar[ij|k] * Br[k]) % mod
r = M-(1 << (N-(ij>>N)))+1
for i in range(0,ij,M):
j = ij-i; l = (1 << (max2(i,j)>>N))-1
for k in range(l,r): Ar[ij|k] += Ar[i|k] * Br[j|k] % mod
return ior_mobius_ranked(Ar, N, M, Z)
def subset_conv(A: list[int], B: list[int], N: int, mod: int) -> list[int]:
Z = (N+1)*(M:=1<<N)
Ar, Br, C, P = [0]*Z, [0]*Z, [0]*M, popcnts(N)
for i, p in enumerate(P): Ar[p<<N|i], Br[p<<N|i] = A[i], B[i]
isubset_conv_ranked(Ar, Br, N, M, Z, mod)
for i, p in enumerate(P): C[i] = Ar[p<<N|i] % mod
return C
def popcnts(N):
P = [0]*(1 << N)
for i in range(N):
for m in range(b := 1<<i):
P[m^b] = P[m] + 1
return P
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_zeta_pair_ranked(A, B, N, M, Z):
for i in range(0, Z, M):
l, r = i+(1<<(i>>N))-1, i+M
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] += A[m^b]; B[m] += B[m^b]; m = m+1|b
return A, B
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
x₀ ────────●─●────────●───●────────●───────●────────► X₀
╳ ╲ ╱ ╲ ╱
x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
╳ ╳ ╲ ╲ ╱ ╱
x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
╳ ╱ ╲ ╲ ╳ ╳ ╱
x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
╳ ╳ ╳ ╳
x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
╳ ╲ ╱ ╱ ╳ ╳ ╲
x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
╳ ╳ ╱ ╱ ╲ ╲
x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
╳ ╱ ╲ ╱ ╲
x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
Math - Convolution
'''
def ior_mobius_ranked(A: list[int], N: int, M: int, Z: int):
for i in range(0, Z, M):
l, r = i, i+M-(1<<(N-(i>>N)))+1
for j in range(N):
m = l|(b := 1<<j)
while m < r: A[m] -= A[m^b]; m = m+1|b
return A
def isubset_deconv_ranked(Ar, Br, N, Z, M, mod):
inv = pow(Br[0], -1, mod); ior_zeta_pair_ranked(Ar, Br, N, M, Z)
for i in range(Z): Br[i], Ar[i] = Br[i]%mod, Ar[i]%mod
for i in range(0, Z, M):
for k in range(M): Ar[i|k] = Ar[i|k] * inv % mod
for j in range(M, Z-i, M):
ij = i + j; l = (1 << (j>>N))-1
for k in range(l,M): Ar[ij|k] -= Ar[i|k] * Br[j|k] % mod
return ior_mobius_ranked(Ar, N, M, Z)
def subset_deconv(A: list[int], B: list[int], N: int, mod: int) -> list[int]:
Z = (N+1)*(M:=1<<N)
Ar, Br, C, P = [0]*Z, [0]*Z, [0]*M, popcnts(N)
for i, p in enumerate(P): Ar[p<<N|i], Br[p<<N|i] = A[i], B[i]
isubset_deconv_ranked(Ar, Br, N, Z, M, mod)
for i, p in enumerate(P): C[i] = Ar[p<<N|i] % mod
return C
F = read(list[int])
G = read(list[int])
H = subset_conv(F, G, N, mod)
write(*H)
assert subset_deconv(H, G, N, mod) == F