Max Convolution
(Convolution/MAX_Convolution.py)

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

Outline

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

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

と定義する.

Code

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

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

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

    """

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

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

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

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

    Less_Zeta_Transform(A)
    Less_Zeta_Transform(B)

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

    Less_Mobius_Transform(A)
    return A

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

    """

    Less_Zeta_Transform(A)
    A=[pow(a,k,Mod) for a in A]
    Less_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

Max Convolution (Convolution/MAX_Convolution.py)

Outline

Code

Max Convolution
(Convolution/MAX_Convolution.py)