//这个题解就是说明一下为什么k==1时要减一
// 因为需要变化一次变为1,所以想当然次数就是s的长度了,比如1,2,4,8等二进制数
// 但是我们发现1变为1所需次数是0,所以最后要把前面组合数C(n,1)算进去的1减去
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7, N = 1e3;
vector<int> fact(N+10), invf(N+10), dp(N+10);
int n, k;
int qmi(int m, int n = mod-2)
{
int res = 1;
while(n)
{
if(n&1)
{
res = 1ll*res*m%mod;
}
m = 1ll*m*m%mod;
n >>= 1;
}
return res;
}
//C(n,m) = n! / m!*(n-m)!
int combin(int n, int m)
{
if(m > n) return 0;
return 1ll*fact[n]*invf[m]%mod*invf[n-m]%mod;
}
int main()
{
fact[0] = invf[0] = 1;
for(int i = 1; i <= N; i ++)
{
fact[i] = 1ll*fact[i-1]*i%mod;
}
invf[N] = qmi(fact[N]);
for(int i = N-1; i >= 1; i --)
{
invf[i] = 1ll*invf[i+1]*(i+1)%mod;
}
string s; cin >> s;
cin >> k;
n = s.size();
dp[1] = 0;
for(int i = 2; i <= 1000; i ++)
{
dp[i] = dp[__builtin_popcount (i)] + 1;
}
int num = 0; int res = 0;
for(int i = 0; i < s.size(); i ++)
{
if(s[i] == '0') continue;
for(int j = max(num, 1); j <= n; j ++)
{
if(dp[j] == k-1)
{
res = (1ll*res + combin(n-i-1, j-num))%mod;
}
}
num ++;
}
if(dp[num] == k-1) res = (res + 1)%mod;
if(k == 0) res = 1;
if(k == 1) res = (res-1+mod)%mod;
cout << res << endl;
return 0;
}