cp_library/bit/popcnts_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Required by

• cp_library/math/conv/mod/isubset_conv_fn.py
• cp_library/math/conv/mod/subset_conv_fn.py
• cp_library/math/conv/subset_conv_fn.py

Verified with

• test/library-checker/set-power-series/subset_convolution.test.py
• test/library-checker/set-power-series/subset_convolution_all.test.py
• test/library-checker/set-power-series/subset_convolution_snippet.test.py

Code

import cp_library.bit.__header__

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

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

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

Back to top page