cp_library/math/conv/ior_mobius_ranked_fn.py

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

Required by

• cp_library/math/conv/isubset_conv_ranked_fn.py
• cp_library/math/conv/isubset_deconv_fn.py
• cp_library/math/conv/isubset_deconv_ranked_fn.py
• cp_library/math/conv/mod/isubset_conv_fn.py
• cp_library/math/conv/mod/isubset_conv_ranked_fn.py
• cp_library/math/conv/mod/isubset_deconv_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/sps/mod/sps_composite_fn.py
• cp_library/math/sps/mod/sps_div_fn.py
• cp_library/math/sps/mod/sps_exp_fn.py
• cp_library/math/sps/mod/sps_ln_adaptive_fn.py
• cp_library/math/sps/mod/sps_ln_fn.py
• cp_library/math/sps/mod/sps_mul_fn.py
• cp_library/math/sps/mod/sps_pow_proj_fn.py
• cp_library/math/sps/mod/sps_pow_proj_poly_fn.py
• cp_library/math/sps/sps_div_fn.py
• cp_library/math/sps/sps_exp_fn.py
• cp_library/math/sps/sps_ln_fn.py
• cp_library/math/sps/sps_mul_fn.py

Verified with

• test/library-checker/set-power-series/exp_of_set_power_series.test.py
• test/library-checker/set-power-series/exp_of_set_power_series_half.test.py
• test/library-checker/set-power-series/polynomial_composite_set_power_series.test.py
• test/library-checker/set-power-series/power_projection_of_set_power_series.test.py
• test/library-checker/set-power-series/subset_convolution.test.py
• test/library-checker/set-power-series/subset_convolution_all.test.py

Code

import cp_library.__header__
import cp_library.math.__header__
import cp_library.math.conv.__header__

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

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             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 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

Back to top page