A41804. $试题 I: 二进制问题【问题描述】小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？【$

填空题困难

知识点

二进制表示数位统计组合计数

题目描述

试题 I: 二进制问题 【问题描述】 小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？ 【输入格式】 输入一行包含两个整数 N 和 K。 【输出格式】 输出一个整数表示答案。 【样例输入】 7 2 【样例输出】 3

#样例不能完全通过
N,K=map(int,input().split())
ans=0
for i in range(1,N+1):
    s=bin(i)[2:]
    
    if s.count("1")==K:
        ans+=1
print(ans)

#C++#include <bits/stdc++.h>#define N 64#define ll long longusing namespace std;ll n;int k;ll dp[N][N], ans = 0;string n2;int get_len(ll x) {    int res = 0;    n2 = "";    while (x) {        if (x % 2 == 0)            n2 = "0" + n2;        else            n2 = "1" + n2;        x >>= 1;        ++res;    }    return res;}void init(int len) {    dp[0][0] = 1;    for (int i = 1; i <= len; ++i) {        for (int j = 0; j <= min(i, k); ++j) {            if (!j) {                dp[i][j] = dp[i - 1][j];            } else {                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];            }        }    }}int main() { scanf("%lld%d", &n, &k);    int len = get_len(n);    init(len);    int cur = 0;    for (int i = 0; i < len; ++i) {        if (n2[i] == '1') ++cur;        ans += (n2[i] - '0') * dp[len - i - 1][k - cur + 1];        if (cur > k) break;    }    if (cur == k) ++ans;    printf("%lld\n", ans);    return 0;}

上一题下一题