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;
}