P17592 Crave Wave (Ver. 2) 题解

哎哎哎，我和 @_O_v_O_ 做的时候只会平方做法啊，结果赛时被爆了 /ll。

首先我们只用关注 的 ，不妨设 ，那么现在要求的是 中有多少个 能在 次操作内变为 。

先考虑在给定 位整数 时，最小化将 变成 的操作次数（允许自然溢出）。手模一下可以发现，如果存在相邻的两位均被操作，那么一定有不劣的操作方案使这两位不同时被操作；当一个操作方案的任意相邻两位都不同时被操作时，这个方案一定是最优的。

例子

• 可被替换为 。
• 可被替换为 。
• 可被替换为 。

考虑对操作次数恰好为 的数计数。对于 ，我们定义其操作序列为：在最优方案中，在每一位上执行的操作所组成的序列。例如 时的操作序列为 ，其中 表示不操作。容易发现操作序列与 构成双射，于是转化为数操作序列。操作序列的限制是：共有 个操作，每个操作是 或 ，且不存在相邻的两个操作。方案数是 。

现在考虑把 变成 的情况，此时的区别是：

• 若 ，那么当 只剩下一位时，我们需要反复进行加操作。例如 ，操作序列为 。
• 若 ，那么当 的高位形成一个连续段时，我们需要反复进行减操作。例如 ，操作序列为 。

容易发现两者基本一样，下面讨论前者。考虑枚举前缀 数量 ，且剩下 位中操作了 次。为了进位， 次操作中的最后一次一定是加操作，且进位后还需要操作 次。因此方案数为：

然而这样会算重。例如 与 本质相同，都表示 。因此当 时，我们需要减去「在从低到高的第 位上进行了加操作」的方案数。后者与前者唯一的区别是 没被算进去，单独加上一即可。

所以答案是：

把内层枚举放到外面，就变成上指标求和了。于是化简后的答案为：

时间复杂度 。

Code

代码中 。

#include <bits/stdc++.h>

#define rep(i, s, e) for(int i = s; i <= (e); ++i)
#define fep(i, s, e) for(int i = s; i < (e); ++i)
#define _rep(i, s, e) for(int i = s; i >= (e); --i)
#define _fep(i, s, e) for(int i = s; i > (e); --i)

// #define int long long
#define pii pair<int, int>

using namespace std;

constexpr int inf = numeric_limits<int>::max() >> 1;
constexpr int ninf = numeric_limits<int>::min() >> 1;
constexpr int mod = 1000000007;
constexpr double eps = 1e-9;

void M(int &x) { x -= (x >= mod ? mod : 0); }

int fac[3005], inv[3005], pw[3005];
int n, k, ans, cur;
string s;

int qpow(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = 1ll * ans * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return ans;
}

int binom(int a, int b) {
	if(a < 0 or b < 0 or a < b) return 0;
	return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;
}

void solve() {
	cin >> n >> k >> s, n = 0, ans = 1;
	while(s.size() and s.back() == '0') {
		++n, s.pop_back();
	}
	rep(i, 1, k) {
		M(cur = binom(n + 2 - i, i + 1) + mod - binom(n - i, i + 1));
		M(cur += mod - binom(n + 1 - k, i + 1));
		M(cur += binom(n - k, i + 1));
		ans = (ans + 1ll * pw[i] * cur) % mod;
	}
	cout << ans << '\n';
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	n = 3002, fac[0] = 1;
	rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	_rep(i, n - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	pw[0] = 1;
	rep(i, 1, n) M(pw[i] = pw[i - 1] << 1);
	int T = 1; cin >> T;
	while(T--) solve();
	return 0;
}