洛谷P17591题解

分析

题意

给定一个二进制表示的大数 $x$ 和整数 $k$，求有多少个数字 $y$，满足至少 $k$ 次规定操作能把 $y$ 变成 $x$。

规定操作：每次对 $y$ 执行 y + lowbit(y) 或 y - lowbit(y)（lowbit(y) 是 $y$ 二进制最低位的数值）。答案对 $10^9+7$ 取模。

思路

1. 先找到 $x$ 二进制末尾连续 $0$ 的长度 $L$。
2. 若要求的操作次数 $k > L$，没有符合条件的 $y$，答案为 $0$；
3. 若 $k \le L$，答案：$2^{L+1} - 2^k$（对 $10^9+7$ 取模）。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int P = 5e6 + 5;
ll pow2[P];
void pre() {
    pow2[0] = 1;
    for (int i = 1; i < P; i++) {
        pow2[i] = (pow2[i - 1] * 2LL) % MOD;
    }
}
const int N = 1e6 + 5;
char s[N];
int main() {
    pre();
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k >> s;
        int L = 0;
        char c = s[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == c) L++;
            else break;
        }
        ll ans;
        if (k > L) ans = 0;
        else ans = (pow2[L + 1] - pow2[k] + MOD) % MOD;
        cout << ans << endl;
    }
    return 0;
}