Min Convolution
(Convolution/MIN_Convolution.py)

View this file on GitHub
Last update: 2021-08-29 23:22:42+09:00

Outline

数列 $A=(A_i)_i, B=(B_j)_j$ に対し, $A,B$ の Min Convolution $A \oplus B$ を

\[A \oplus B:=\left(\sum_{\min(i,j)=k} A_i B_j \right)_k\]

と定義する.

Code

def More_Zeta_Transform(A):
    """ A の以上を走る Zeta 変換を行う.

    """
    for i in range(len(A)-2,-1,-1):
        A[i]=(A[i]+A[i+1])%Mod

def More_Mobius_Transform(A):
    """ A の以下を走るにおける Mobius 変換を行う.

    """

    for i in range(len(A)-1):
        A[i]=(A[i]-A[i+1])%Mod

def Convolution_MIN(A,B):
    """ A,B の min における畳み込みを行う.
    """

    N=len(A); M=len(B)
    L=max(N,M)

    A=A+[0]*(L-N)
    B=B+[0]*(L-M)

    More_Zeta_Transform(A)
    More_Zeta_Transform(B)

    for i in range(L):
        A[i]*=B[i]
        A[i]%=Mod

    More_Mobius_Transform(A)
    return A

def Convolution_Power_MIN(A,k):
    """ A の min における k 回の畳み込みを行う.

    """
    A=A[:]
    More_Zeta_Transform(A)
    A=[pow(a,k,Mod) for a in A]
    More_Mobius_Transform(A)
    return A

Mod=998244353

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Min Convolution (Convolution/MIN_Convolution.py)

Outline

Code

Min Convolution
(Convolution/MIN_Convolution.py)