[CF914C] Travelling Salesman and Special Numbers

[CF914C] Travelling Salesman and Special Numbers - 组合计数

Description

对于一个正整数x，我们定义一次操作是将其变为它二进制下“1”的个数。给定n和k，其中n是在二进制下被给出，求出所有不大于n且将其变为1的操作次数为k的数的个数对。(x le 2^{1000})

Solution

一个数操作一次以后，一定会变成不超过 1000 的数

我们先暴力计算出所有不超过 1000 的数的答案

然后考虑一个类似数位 dp 的过程

我们去试图把给定数的某个 1 改成 0，那么后面的位置都可以随便选

在这种可以随便选的情况下，我们就要加上若干个组合数乘以某个不超过 1000 的数的答案是否刚好等于 k 的形式

这样总的复杂度是 O(n^2) 的，n 为原数的长度

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

namespace math_mod
{
    int c__[5005][5005], fac__[5005];

    int qpow(int p, int q)
    {
        return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
    }

    int inv(int p)
    {
        return qpow(p, mod - 2);
    }

    int fac(int p)
    {
        if (p <= 5000)
            return fac__[p];
        if (p == 0)
            return 1;
        return p * fac(p - 1) % mod;
    }

    int __fac(int p)
    {
        return fac(p);
    }

    int ncr(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        return fac(n) * inv(fac(r)) % mod * inv(fac(n - r)) % mod;
    }

    void math_presolve()
    {
        fac__[0] = 1;
        for (int i = 1; i <= 5000; i++)
        {
            fac__[i] = fac__[i - 1] * i % mod;
        }
        for (int i = 0; i <= 5000; i++)
        {
            c__[i][0] = c__[i][i] = 1;
            for (int j = 1; j < i; j++)
                c__[i][j] = c__[i - 1][j] + c__[i - 1][j - 1], c__[i][j] %= mod;
        }
    }

    int __c(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        if (n > 5000)
            return ncr(n, r);
        return c__[n][r];
    }
}

using namespace math_mod;

int f[1005], a[1005], n;

void solve_1000()
{
    f[1] = 0;
    for (int i = 2; i <= 1000; i++)
    {
        int cnt = __builtin_popcount(i);
        f[i] = f[cnt] + 1;
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    solve_1000();

    math_presolve();

    string str;
    cin >> str;
    int k;
    cin >> k;

    if (k == 0)
    {
        cout << 1 << endl;
        return 0;
    }

    n = str.length();
    for (int i = 1; i <= n; i++)
        a[i] = str[i - 1] == '1';

    int ans = 0;
    int sum = 0; // previous 1-count

    // enum the first different position
    for (int i = 1; i <= n; i++)
    {
        // if a[i]==0, then no contribution
        if (a[i] == 0)
            continue;
        // if a[i]==1, then the rest positions can be filled with any digits
        int res = n - i;
        for (int j = 0; j <= res; j++)
        {
            // choose j positions in rest positions to fill with 1
            int cnt = j + sum; // total 1 count
            int val = f[cnt] + 1;
            if (val == k)
            {
                // ok, make countribution
                ans += __c(res, j);
                ans %= mod;
            }
        }
        sum++;
    }

    // add itself
    if (f[sum] + 1 == k)
        ans++, ans %= mod;

    if (k == 1)
        ans = (ans - 2 + mod) % mod;

    cout << ans << endl;
}