AcWing 1081. 度的数量

◎

本节目标

在进制上界内统计只含 0 和 1 且恰有 k 个 1 的数。

题意与约束

统计闭区间内：在 base 进制表示中只含 0、1 且恰有 k 个 1 的整数。

第一反应与重复子问题

从左到右决定数位时，剩余选择只依赖当前位置、已用 1 数和是否贴着上界。

状态定义与转移推导

定义 F(limit) 的数位 DFS：position、ones、tight。当前位只枚举 0 和 1，区间答案为 F(right)-F(left-1)。

正确性依据

每个不超过上界的合法进制表示对应唯一的数位选择序列；限制候选位为 0/1 正好排除了其他非零位。

样例执行过程

在二进制 15..20 中，17、18、20 恰有两个 1，答案为 3。

代码实现

C++

C++17

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int countDegreeUpTo(int limit, int k, int base) {
    if (limit < 0) {
        return 0;
    }
    vector<int> digits;
    while (true) {
        digits.push_back(limit % base);
        limit /= base;
        if (limit == 0) {
            break;
        }
    }
    reverse(digits.begin(), digits.end());
    int length = static_cast<int>(digits.size());
    vector<vector<int>> memo(length, vector<int>(k + 1, -1));
    function<int(int, int, bool)> dfs = [&](int position, int ones, bool tight) -> int {
        if (ones > k) {
            return 0;
        }
        if (position == length) {
            return ones == k;
        }
        if (!tight && memo[position][ones] != -1) {
            return memo[position][ones];
        }
        int result = 0;
        int upper = tight ? digits[position] : base - 1;
        for (int digit = 0; digit <= min(upper, 1); digit++) {
            result += dfs(position + 1, ones + (digit == 1), tight && digit == upper);
        }
        if (!tight) {
            memo[position][ones] = result;
        }
        return result;
    };
    return dfs(0, 0, true);
}

int countDegreeNumbers(int left, int right, int k, int base) {
    return countDegreeUpTo(right, k, base) - countDegreeUpTo(left - 1, k, base);
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int left;
    int right;
    int k;
    int base;
    if (cin >> left >> right >> k >> base) {
        cout << countDegreeNumbers(left, right, k, base);
    }
}
#endif

Python

Python 3

import sys


def _count_degree_up_to(limit, k, base):
    if limit < 0:
        return 0
    digits = []
    while True:
        digits.append(limit % base)
        limit //= base
        if not limit:
            break
    digits.reverse()
    memo = {}

    def dfs(position, ones, tight):
        if ones > k:
            return 0
        if position == len(digits):
            return int(ones == k)
        if not tight and (position, ones) in memo:
            return memo[position, ones]
        upper = digits[position] if tight else base - 1
        result = sum(dfs(position + 1, ones + (digit == 1), tight and digit == upper) for digit in range(min(upper, 1) + 1))
        if not tight:
            memo[position, ones] = result
        return result

    return dfs(0, 0, True)


def count_degree_numbers(left, right, k, base):
    return _count_degree_up_to(right, k, base) - _count_degree_up_to(left - 1, k, base)


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if data:
        print(count_degree_numbers(*data))


if __name__ == '__main__':
    main()

复杂度分析

状态为位数与 ones 的乘积，时间和空间均为 O(dk)。

边界与易错点

三进制的 2 不是一个 1；k 大于可用位数时直接没有方案。

模式迁移

限制是计数而非去重时用计数状态；需要禁止重复数字时加入位掩码。回到数位动态规划。