| from collections import defaultdict
|
| from math import comb
|
|
|
| def rank_counts(n, k):
|
| # C_{n,k}: each upper element covers k+1 consecutive lower elements
|
| coeff = [0] * (2*n + 1)
|
| all_ones = (1 << k) - 1
|
|
|
| for first_mask in range(1 << k):
|
| first_bits = [(first_mask >> i) & 1 for i in range(k)]
|
| dp = {(first_mask, sum(first_bits), 0): 1}
|
|
|
| for pos in range(k, n):
|
| ndp = defaultdict(int)
|
| for (mask, ones, a), cnt in dp.items():
|
| for b in (0, 1):
|
| new_ones = ones + b
|
| new_a = a + (mask == all_ones and b == 1)
|
| new_mask = (mask >> 1) | (b << (k - 1))
|
| ndp[(new_mask, new_ones, new_a)] += cnt
|
| dp = ndp
|
|
|
| for (mask, ones, a), cnt in dp.items():
|
| last_bits = [(mask >> i) & 1 for i in range(k)]
|
| wrap = 0
|
| for j in range(k):
|
| if all(last_bits[j:] + first_bits[:j+1]):
|
| wrap += 1
|
|
|
| a += wrap
|
| for q in range(a + 1):
|
| coeff[ones + q] += cnt * comb(a, q)
|
|
|
| return coeff
|
|
|
| c = rank_counts(37, 6)
|
| print(c[20:25])
|