cp_library/math/sps/mod/sps_ln_small_fn.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00

Required by

• cp_library/math/sps/mod/sps_ln_adaptive_fn.py

Code

import cp_library.__header__
import cp_library.math.__header__
import cp_library.math.sps.__header__

def sps_ln_small(P, mod):
    assert P[0] == 1
    ln = [0]*(Z:=1<<(N:=len(P).bit_length()-1))
    for i in range(1, Z):
        fg, b, j = 0, 1<<(i.bit_length()-1), i-1&i
        while b <= j: fg += ln[j]*P[i^j]%mod; j = j-1&i
        ln[i] = (P[i]-fg)%mod
    return ln

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''



def sps_ln_small(P, mod):
    assert P[0] == 1
    ln = [0]*(Z:=1<<(N:=len(P).bit_length()-1))
    for i in range(1, Z):
        fg, b, j = 0, 1<<(i.bit_length()-1), i-1&i
        while b <= j: fg += ln[j]*P[i^j]%mod; j = j-1&i
        ln[i] = (P[i]-fg)%mod
    return ln

Back to top page