思路
- 显然，(a_{i} = c^{popcount(i)})。
- 由于n的范围是([0,2^{3000}])，所以肯定不能从头加到尾
- 对于n=满二进制111时，那么结果为(C_{3}^{0}*c^{0}+C_{3}^{1}*c^{1}+C_{3}^{2}*c^{2}+C_{3}^{3}*c^{3})（这部分可以预处理）
- 那么，对于1000，其结果就是满二进制结果再加上c（也就是ans先初始化为1）
- 此时如果要计算101000，我们从右往左遍历
- 遍历到101000，先计算出1000的结果，也就是[0,1000)，设为x
- 然后再遍历到101000，同样可以计算出[0，100000)，那么，另外的[100000，101000)呢？
- 显然就是[0,1000)的结果前面都加上一个1，也就是(x * c)
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
long long C[3005][3005];
long long sum[3005];
int main(){
char n[3005];
int c;
long long ans = 1;
cin >> n >> c;
int len = strlen(n);
for (int i = 0;i <= len;i++ ) {
C[i][0] = 1;
sum[i] = 1L;
long long temp = c;
for (int j = 1;j <= i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j])%mod;
sum[i] = (sum[i] + (C[i][j]*temp) % mod) % mod;
temp = temp * c % mod;
}
}
for (int i = len - 1;i >= 0;i--) {
if (n[i] == '1') {
ans = (ans*c%mod + sum[len - i - 1]) % mod;
}
}
cout << ans << endl;
return 0;
}