题解： Minimum OR is X

Problem Statement

给定三个正整数 (N, M, K) 和非负整数 (X) 。

求出有多少个满足以下条件的长为 (N) 的非负整数列 (A = (A_1, A_2, cdots, A_N)) 个数，答案对 ( m 998244353) 取模：

• (0le A_i le 2 ^ M - 1 (1le ile N))
• 数列 (A) 中任意选择 (K) 个位置 (i_1, i_2, cdots, i_K (i_a eq i_b)) ，满足 (min{A_{i_1}oplus A_{i_2}opluscdotsoplus A_{i_K}} = X) 。

其中 (oplus) 运算代表 C++ 中的按位或运算。

Constraints

(1le N, Mle 200) ，(1le K le N) ，(0le Xle 2 ^ M - 1) ，(X) 以二进制字符串的形式给出。

solution

从高到低按位贪心，发现对于每一层，如果有 (ge K) 个 0 那么这一位必定为 0 ，否则为 1 。

那么贪心取 0 的时候，那么所有该层为 1 的元素都不能取了，所以在考虑下面层的时候，这些元素就不能考虑了。

对于这个过程设计一个 DP ，设 (f(i, j)) 表示从高到低到第 (i) 位，还有 (j) 个元素能取的方案数。

对于贪心的方案，设计两种转移:

• (X) 该位为 0 ，设 (k) 为该层 1 的个数。
• • (f(i, j) leftarrow displaystylesum_{k = 0} ^ {n - K} f(i + 1, j + k) imes dbinom{j + k}{j} imes 2 ^ {k(i - 1)})
• (X) 该位为 1 ，设 (k) 为该层 0 的个数。
• • (f(i, j) leftarrow f(i + 1, j) imes displaystyle{sum_{k = 0} ^ {K - 1}}dbinom{j}{k})

答案就是 (sum f(0, i)) 。

Mint fac[N << 1], ifac[N << 1];
inline void table(int lim) {
	fac[0] = Mint(1);
	forn (i, 1, lim) fac[i] = fac[i - 1] * Mint(i);
	ifac[lim] = q_pow(fac[lim]);
	form (i, lim - 1, 0) ifac[i] = ifac[i + 1] * Mint(i + 1);
}
inline Mint C(int n, int r) {
	if (n < 0 || r < 0 || n < r) return Mint(0);
	return fac[n] * ifac[r] * ifac[n - r];
}
int n, m, K; char X[N]; Mint f[N][N];
inline void solve() {
	Rdn(n, m, K); Rdn(X); table(max(n, m) << 1);
	reverse(X, X + m);
	f[m][n] = Mint(1);
	form (i, m - 1, 0) forn (j, 0, n) {
		if (X[i] == '0') {
			if (j >= K) forn (k, 0, n - K) if (j + k <= n) {
				f[i][j] += f[i + 1][j + k] * C(j + k, k) * q_pow(Mint(2), k * i);
			}
		} else {
			forn (k, 0, K - 1) f[i][j] += f[i + 1][j] * C(j, k);
		}
	}
	Mint res(0);
	forn (i, 0, n) res += f[0][i];
	Wtn(res.res, '
');
}