题意
定义对一个整数\(x\)的操作\(f(x)\)为把\(x\)变换为其二进制表示中\(1\)的个数。给定\(n,k\),请求出\(1\)至\(n\)中经过\(k\)次变换恰好变成\(1\)的数的个数
\(n\leq 2^{1000},k\leq1000\)
解法
这题考场上想出来了,但是!打萎了
主要还是数位\(DP\)打得不多,还有一些边界情况没有考虑
稍微想一想就能知道\(1000\)至\(2^{1000}\)的任何数经过一次\(f\)变换后都会落入\(1\)至\(1000\)的区间内
我们预处理出一个数组\(a\),\(a_i\)表示二进制位中\(1\)的个数为\(i\)的数要经过多少次变换可以变为\(1\)
接下来我们的任务就是求出\(1\)到\(n\)中二进制位中\(1\)的个数为\(i\)的数有多少个,用数组\(b_i\)存储
这个可以用数位\(DP\)处理
最后扫一遍统计答案即可
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10;
const int mod = 1e9 + 7;
int n, k;
int a[N], b[N], d[N];
long long f[N][N][2], c[N];
char s[N];
int solve(int x) {
int res = 0;
while (x != 1) {
int btc = 0;
while (x)
btc += (x & 1), x >>= 1;
x = btc;
++res;
}
return res;
}
int main() {
// freopen("number.in", "r", stdin);
// freopen("number.out", "w", stdout);
scanf("%s", s + 1);
scanf("%d", &k);
if (k >= 1000)
return puts("0"), 0;
if (k == 0)
return puts("1"), 0;
n = strlen(s + 1);
for (int i = 1; i <= n; ++i)
a[i] = s[i] - 48;
if (n == 1)
return puts("0"), 0;
for (int i = 1; i <= 1000; ++i) b[i] = solve(i) + 1;
f[1][1][1] = 1, f[1][0][0] = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] == 0) {
f[i][0][0] = f[i - 1][0][0];
for (int j = 1; j <= i; ++j)
f[i][j][0] = (f[i - 1][j - 1][0] + f[i - 1][j][0]) % mod,
f[i][j][1] = f[i - 1][j][1];
} else {
f[i][0][0] = f[i - 1][0][0];
for (int j = 1; j <= i; ++j)
f[i][j][0] = ((f[i - 1][j - 1][0] + f[i - 1][j][0]) % mod + f[i - 1][j][1]) % mod,
f[i][j][1] = f[i - 1][j - 1][1];
}
}
for (int i = 1; i <= 1000; ++i)
c[i] = (f[n][i][0] + f[n][i][1]) % mod;
long long ans = 0;
for (int i = 1; i <= 1000; ++i)
if (b[i] == k)
ans = (ans + c[i]) % mod;
if (k == 1) --ans;
printf("%lld\n", (ans + mod) % mod);
return 0;
}