Олимпиада по информатике 2025-2026 муниципальный этап Хомяк и двоичные тайны

Олимпиада по информатике 2025-2026 муниципальный этап Хомяк и двоичные тайны

olimp-inf-tatmunits-2025-D

Скачать

1. Что делает твой алгоритм (коротко)

Задача: посчитать количество чисел x таких, что
0 ≤ x ≤ R и popcount(x) ≡ 0 (mod K).

Твой код делает следующее:

Читает n, K, R (где R — десятичная строка).
Переводит R в двоичную строку bin_str.
Пусть L = len(bin_str) – длина двоичной записи R.
Частный случай K > L
Тогда popcount(x) никогда не может быть K, 2K, ...,
единственный вариант с popcount(x) = 0 — это x = 0.
0 ≤ R всегда верно, поэтому ответ = 1.
Если K небольшой (≤ 120) — запускается битовый DP по модулю K:
- Состояния:
  - dp_tight[r] – сколько чисел с остатком r по popcount mod K,
    у которых префикс точно совпадает с префиксом R.
  - dp_loose[r] – сколько чисел с остатком r,
    у которых префикс уже строго меньше префикса R.
- Идем по битам R слева направо, на каждом шаге:
  - если бит R равен 0, в состоянии tight можно поставить только 0;
  - если бит R равен 1, можно поставить 0 (становимся loose)
    или 1 (остаемся tight, увеличиваем popcount).
  - из loose можно ставить и 0, и 1 всегда.
- В конце ответ = dp_tight[0] + dp_loose[0] (все числа, где popcount % K == 0).
Сложность ~ O(L * K).
Если K большой – используется комбинаторика:
- Сначала предвычисляем факториалы и обратные факториалы до L
  для биномиальных коэффициентов C(n, r) по модулю.
- Функция count_with_exact_ones(c, bin_str, ...) считает,
  сколько чисел x, 0 ≤ x ≤ R, имеют ровно c единиц в двоичной записи.
  Это делается классическим приёмом:
  - идём по битам R,
  - когда в R стоит 1, есть вариант «поставить 0 здесь, а дальше выбрать need единиц» → добавляем C(remaining, need),
  - и вариант «поставить 1 и уменьшить need».
- Затем перебираем c = 0, K, 2K, ... пока c ≤ L
  и суммируем count_with_exact_ones(c, ...).
Это эффективно, когда K достаточно большой, так как тогда возможных c немного (примерно L / K).

2. Почему в Python 3 — 90 баллов, а в PyPy — 100?

По условиям задачи:
в последней группе тестов n ≤ 30000, значит:

длина двоичной записи R ≈ L ≈ n * log10(2) ≈ 100 000 бит;
при небольших K (например, K = 2, 3, …, 120)
мы попадаем в ветку solve_small_K, т.е. выполняем DP сложностью:

$\cdot K) \approx 100000 \cdot 120 = 12\,000\,000 \text{ переходов}$

Для C++/Pascal это легко в 1 секунду,
но чистый CPython 3.10 с такими плотными циклами по спискам
часто не успевает в лимит 1 секунда →
на самой большой группе тестов получается TLE или слишком долгий запуск,
и система ставит «Частичное решение: 90 баллов».

У PyPy 3.10-64:

есть JIT-компиляция,
длинные однотипные циклы сильно ускоряются,

и тот же самый код успевает за отведённое время → 100 баллов.

То есть:

Алгоритм у тебя абсолютно корректный (это видно по 100% в PyPy);
Проблема именно в производительности CPython на последней группе (n = 30000).

import sys

MOD = 10**9 + 7
SMALL_K_LIMIT = 120  # порог, когда выгодно делать DP по модулю

# Снимаем ограничение Python 3.11+ на длину строки для int(...)
if hasattr(sys, "set_int_max_str_digits"):
    sys.set_int_max_str_digits(0)

data = sys.stdin.read().strip().split()
if not data:
    sys.exit(0)

n = int(data[0])     # длина десятичной записи R (по сути не нужна)
K = int(data[1])
R_str = data[2]

# --- перевод R в двоичную запись ---
R_int = int(R_str)
bin_str = bin(R_int)[2:]
L = len(bin_str)

# --- частный случай K > L ---
if K > L:
    # popcount(x) не может быть K, 2K, ... => только popcount(x) = 0, т.е. x = 0
    # 0 всегда <= R, поэтому ответ = 1
    print(1)
    sys.exit(0)

# --- Вариант 1: DP по битам по остатку popcount mod K ---
def solve_small_K(bin_str, K):
    L = len(bin_str)
    # dp_tight[r]  - кол-во чисел с остатком r, префикс равен префиксу R
    # dp_loose[r]  - кол-во чисел с остатком r, префикс уже меньше R
    dp_tight = [0] * K
    dp_loose = [0] * K
    dp_tight[0] = 1  # ещё не выбрали ни одного бита

    for ch in bin_str:
        bit = 1 if ch == '1' else 0

        new_tight = [0] * K
        new_loose = [0] * K

        # переходы из tight-состояний
        if bit == 0:
            # можем поставить только 0, остаёмся tight
            for r in range(K):
                val = dp_tight[r]
                if val:
                    new_tight[r] = (new_tight[r] + val) % MOD
        else:
            # бит R = 1, можем поставить 0 или 1
            for r in range(K):
                val = dp_tight[r]
                if not val:
                    continue
                # ставим 0 -> становимся loose
                new_loose[r] = (new_loose[r] + val) % MOD
                # ставим 1 -> остаёмся tight, popcount+1
                nr = r + 1
                if nr >= K:
                    nr -= K
                new_tight[nr] = (new_tight[nr] + val) % MOD

        # переходы из loose-состояний (уже < R, можно ставить 0 или 1)
        for r in range(K):
            val = dp_loose[r]
            if not val:
                continue
            # ставим 0
            new_loose[r] = (new_loose[r] + val) % MOD
            # ставим 1
            nr = r + 1
            if nr >= K:
                nr -= K
            new_loose[nr] = (new_loose[nr] + val) % MOD

        dp_tight, dp_loose = new_tight, new_loose

    # числа с popcount % K == 0
    return (dp_tight[0] + dp_loose[0]) % MOD

# --- Вариант 2: комбинаторика по точному числу единиц ---
def precompute_fact(L):
    fact = [1] * (L + 1)
    for i in range(1, L + 1):
        fact[i] = fact[i - 1] * i % MOD
    invfact = [1] * (L + 1)
    invfact[L] = pow(fact[L], MOD - 2, MOD)
    for i in range(L, 0, -1):
        invfact[i - 1] = invfact[i] * i % MOD
    return fact, invfact

def nCr(n, r, fact, invfact):
    if r < 0 or r > n:
        return 0
    return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD

def count_with_exact_ones(c, bin_str, fact, invfact):
    """
    Кол-во x, 0 <= x <= R, таких что popcount(x) = c.
    """
    L = len(bin_str)
    need = c
    ans = 0

    for i, ch in enumerate(bin_str):
        bit = 1 if ch == '1' else 0
        remaining = L - i - 1

        if bit == 1:
            # ставим 0 здесь -> дальше любое число с ровно need единицами
            if need >= 0:
                ans = (ans + nCr(remaining, need, fact, invfact)) % MOD
            # ставим 1 здесь -> уменьшаем need и идём дальше
            need -= 1
            if need < 0:
                break
        else:
            # бит R = 0, можем поставить только 0, need не меняется
            pass

    else:
        # дошли до конца без break: если need == 0, считаем само R
        if need == 0:
            ans = (ans + 1) % MOD

    return ans

def solve_large_K(bin_str, K):
    L = len(bin_str)
    fact, invfact = precompute_fact(L)
    total = 0
    # перебираем c = 0, K, 2K, ...
    c = 0
    while c <= L:
        total = (total + count_with_exact_ones(c, bin_str, fact, invfact)) % MOD
        c += K
    return total

# --- выбор подхода и вывод ответа ---
if K <= SMALL_K_LIMIT:
    ans = solve_small_K(bin_str, K)
else:
    ans = solve_large_K(bin_str, K)

print(ans)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

import sys

MOD = 10**9 + 7

SMALL_K_LIMIT = 120 # порог, когда выгодно делать DP по модулю

# Снимаем ограничение Python 3.11+ на длину строки для int(...)

if hasattr(sys, "set_int_max_str_digits"):

sys.set_int_max_str_digits(0)

data = sys.stdin.read().strip().split()

if not data:

sys.exit(0)

n = int(data[0]) # длина десятичной записи R (по сути не нужна)

K = int(data[1])

R_str = data[2]

# --- перевод R в двоичную запись ---

R_int = int(R_str)

bin_str = bin(R_int)[2:]

L = len(bin_str)

# --- частный случай K > L ---

if K > L:

# popcount(x) не может быть K, 2K, ... => только popcount(x) = 0, т.е. x = 0

# 0 всегда <= R, поэтому ответ = 1

print(1)

sys.exit(0)

# --- Вариант 1: DP по битам по остатку popcount mod K ---

def solve_small_K(bin_str, K):

L = len(bin_str)

# dp_tight[r] - кол-во чисел с остатком r, префикс равен префиксу R

# dp_loose[r] - кол-во чисел с остатком r, префикс уже меньше R

dp_tight = [0] * K

dp_loose = [0] * K

dp_tight[0] = 1 # ещё не выбрали ни одного бита

for ch in bin_str:

bit = 1 if ch == '1' else 0

new_tight = [0] * K

new_loose = [0] * K

# переходы из tight-состояний

if bit == 0:

# можем поставить только 0, остаёмся tight

for r in range(K):

val = dp_tight[r]

if val:

new_tight[r] = (new_tight[r] + val) % MOD

else:

# бит R = 1, можем поставить 0 или 1

for r in range(K):

val = dp_tight[r]

if not val:

continue

# ставим 0 -> становимся loose

new_loose[r] = (new_loose[r] + val) % MOD

# ставим 1 -> остаёмся tight, popcount+1

nr = r + 1

if nr >= K:

nr -= K

new_tight[nr] = (new_tight[nr] + val) % MOD

# переходы из loose-состояний (уже < R, можно ставить 0 или 1)

for r in range(K):

val = dp_loose[r]

if not val:

continue

# ставим 0

new_loose[r] = (new_loose[r] + val) % MOD

# ставим 1

nr = r + 1

if nr >= K:

nr -= K

new_loose[nr] = (new_loose[nr] + val) % MOD

dp_tight, dp_loose = new_tight, new_loose

# числа с popcount % K == 0

return (dp_tight[0] + dp_loose[0]) % MOD

# --- Вариант 2: комбинаторика по точному числу единиц ---

def precompute_fact(L):

fact = [1] * (L + 1)

for i in range(1, L + 1):

fact[i] = fact[i - 1] * i % MOD

invfact = [1] * (L + 1)

invfact[L] = pow(fact[L], MOD - 2, MOD)

for i in range(L, 0, -1):

invfact[i - 1] = invfact[i] * i % MOD

return fact, invfact

def nCr(n, r, fact, invfact):

if r < 0 or r > n:

return 0

return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD

def count_with_exact_ones(c, bin_str, fact, invfact):

"""

Кол-во x, 0 <= x <= R, таких что popcount(x) = c.

"""

L = len(bin_str)

need = c

ans = 0

for i, ch in enumerate(bin_str):

bit = 1 if ch == '1' else 0

remaining = L - i - 1

if bit == 1:

# ставим 0 здесь -> дальше любое число с ровно need единицами

if need >= 0:

ans = (ans + nCr(remaining, need, fact, invfact)) % MOD

# ставим 1 здесь -> уменьшаем need и идём дальше

need -= 1

if need < 0:

break

else:

# бит R = 0, можем поставить только 0, need не меняется

pass

else:

# дошли до конца без break: если need == 0, считаем само R

if need == 0:

ans = (ans + 1) % MOD

return ans

def solve_large_K(bin_str, K):

L = len(bin_str)

fact, invfact = precompute_fact(L)

total = 0

# перебираем c = 0, K, 2K, ...

c = 0

while c <= L:

total = (total + count_with_exact_ones(c, bin_str, fact, invfact)) % MOD

c += K

return total

# --- выбор подхода и вывод ответа ---

if K <= SMALL_K_LIMIT:

ans = solve_small_K(bin_str, K)

else:

ans = solve_large_K(bin_str, K)

print(ans)