题解：CF914C Travelling Salesman and Special Numbers

linjinkun · 2026-01-27 21:30:59 · 题解

妙妙题。

一看到 1 \le n<2^{1000} 直接就吓晕了，但仔细一想，n 最大 2^{1000}-1，转成二进制的话相当于 1000 个 1 排在一起，做了一次操作后，其实就变成 1000 而已，于是我们很容易想到预处理 1 \sim 1000 的需要操作的次数，然后再进行数位 DP 即可。记得在 DFS 中维护一个 d 变量，表示目前有多少个 1。

最后简单说一下如何预处理，就是搞一个 cnt 数组，然后 cnt_i = cnt_{f(i)}+1，这里的 f(i) 是指 i 的二进制形式中 1 的个数，f(i) 并不需要很复杂的计算，因为 __builtin 类函数中有一个 __builtin_popcount 函数，刚好就是求一个数在二进制下 1 的个数，时间复杂度 O(1)，并且没有什么常数。

::::warning[注意] 考虑到 1 需要的操作次数其实是 0，但是如果用 cnt_s+1 = k 这个判断来判断这个数是否是操作 k 次的话，就会误判，所以要特殊处理 k = 0 和 k = 1 的情况，一个是会少判，一个是会多判。

并且 k = 1 的特判并不能直接减 1，因为考虑到要对 10^9+7 进行取模，如果为 0，减 1 的话就是 -1，直接炸了，还要加上 10^9+7 再对 10^9+7 取模。 :::: ::::success[Code]

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
string a;
int n,k;
int f[1005][2][1005];
int cnt[1005];
int dfs(int x,int ding,int d)
{
    if(x == n)
    {
        if(!d)
        {
            return 0;
        }
        return (cnt[d]+1 == k);
    }
    if(f[x][ding][d]!=-1)
    {
        return f[x][ding][d];
    }
    int ans = 0;
    for(int i = 0;i<=(ding?a[x]-'0':1);++i)
    {
        int dingg = ding&&i == a[x]-'0';
        ans = (ans+dfs(x+1,dingg,d+i))%mod;
    }
    return f[x][ding][d] = ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> k;
    if(k == 0)
    {
        cout << 1;
        return 0;
    }
    for(int i = 2;i<=1000;++i)
    {
        cnt[i] = cnt[__builtin_popcount(i)]+1;
    }
    n = a.size();
    memset(f,-1,sizeof(f));
    if(k == 1)
    {
        cout << (dfs(0,1,0)-1+mod)%mod;
        return 0;
    }
    cout << dfs(0,1,0);
    return 0;
}

::::