prologue
模拟赛的一道题，结果没做出来，丢大人，败大兴。所以过来糊一篇题解。
analysis
我们看到数据范围这么大，那么肯定不可以一个一个遍历（废话），所以就要考虑这个题目的性质。
我们先假设，极端数据 \(2 ^ {1000} - 1\)，这个数字中包含了 \(999\) 个 1（正好感冒了能不能让我喝了）。下一次的数据就是 \(999\)，这个时候，\(999\) 的二进制表示为 \(11 1110 0111\)，下次就是 \(8\)，再下次就是 \(1\) 了。这个时候的最少变换次数是 \(3\)。
我们看到这个数据缩小是很快的。那我们再进一步研究观察。
由于上限原因，所以我们第一次变换之后的数字一定为 \(\le 1000\) 的数字。我们又知道（不知道的掏计算器） \(2 ^ {10} = 1024\) 已经大于 1000 了，为了方便统计，适当放大数据。下次需要进行操作的数字就变成了 $ [0, 10] $ 就更小了，这个时候手搓一下，发现 \(7\) 这个数据是 \([0, 10]\) 之间的二进制表示下包含 1 最多的一个数字。
我们就求出来了这个恰好变换次数的上限。对于 100% 的数据而言，一定有：
- \(2 \le k \le 5\) 有解。
- \(k > 5\) 无解。
这个时候特判两个情况：
- \(k = 1\) 时，答案的个数为 \(length_s - 1\)。
- \(k = 0\) 时，答案为 1（只有 1 这种情况）。
我们之后就去考虑怎么计算这个值。
我们可以考虑一种类似于数位 dp 的思想，从高位往低位，用 \(f[i][j]\) 表示已经填了 i 个 1，剩下 j 位随便填，并且恰好 k 次变换之后能够变成 1 的方案数。
考虑递推式，从定义出发，预处理出来可能的值：
\[f[i][j] \gets f[i - 1][j] \]\[f[i][j] \gets f[i][j] + f[i - 1][j + 1], (j \le n - 1) \]计算方案数量：
\[res \gets (res + f[n - i - 1][t ++ ]) % P \]注意，如果我们最后的这个数字符合我们的最后变换数量少一，就是最后可以变到 1，我们要给方案数加 1。
code time
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define endl '\n'
const ll N = 1010, P = 1e9 + 7;
char ch[N];
ll n, m, g[N], f[N][N];
int main()
{
scanf("%s%lld", ch, &m);
n = strlen(ch);
if(m == 0) puts("1");
else if(m == 1) cout << n - 1 << endl;
else if(m > 5) cout << "0" << endl;
else
{
for(rl i=2; i <= 1000; ++ i)
{
ll cnt = 0;
for(rl j=i; j; j >>= 1)
if(j & 1) cnt ++;
g[i] = g[cnt] + 1;
}
for(rl i=1; i <= n; ++ i) f[0][i] = g[i] == m - 1;
for(rl i=1; i <= n; ++ i)
for(rl j=0; j <= n; ++ j)
{
f[i][j] = f[i - 1][j];
if(j + 1 <= n) f[i][j] = (f[i][j] + f[i-1][j + 1]) % P;
}
ll res = 0, t = 0;
for(rl i=0; i < n; ++ i)
if(ch[i] == '1')
{
res = (res + f[n - i - 1][t]) % P; t ++ ;
}
if(g[t] == m - 1) cout << res + 1 << endl;
else cout << res << endl;
}
return 0;
}