自动搬运

查看原文

来自洛谷，原作者为

	SDqwq 少年何妨梦摘星，敢挽桑弓射玉衡。

搬运于2025-08-24 22:34:41，当前版本为作者最后更新于2021-12-05 16:02:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

传送门

$\texttt{Description}$

题面很友好，略。

$\texttt{Data Range:}1\le k\le n\le30,0\le m\le100,1\le v_i<998244353$

$\texttt{Solution}$

看到这种题容易想到 dp。

我们发现，$S$ 的二进制表示位中 $1$ 的数量会涉及进位的问题。由于进位是从低位向高位进行的，所以考虑在 $S$ 中从低位到高位按位 dp（最低位为第 $0$ 位）。

设计 dp 状态 $f(i,j,k,p)$ 表示：讨论了 $S$ 从低到高的前 $i$ 位，已经确定了 $j$ 个序列 $a$ 中的元素，$S$ 从低到高前 $i$ 位中有 $k$ 个 $1$，要向当前讨论位的下一位进位 $p$。

因为从上一个状态转移到 $f(i,j,k,p)$ 细节太多，所以考虑用 $f(i,j,k,p)$ 往后转移。

接下来讨论第 $i$ 位（位从 $0$ 开始编号）。假设序列 $a$ 中有 $t$ 个元素为 $i$，那么就相当于给 $S$ 的第 $i$ 位贡献了 $t$ 个 $1$，再加上上一位进过来的 $p$ 个 $1$，总共有 $t+p$ 个 $1$。

我们知道，当前位每两个 $1$ 可以向下一位进一个 $1$。所以 $(t+p)\bmod2$ 的结果即为全部进位后当前位是否为 $1$。同理，向下一位进的 $1$ 的个数即为 $\left\lfloor\frac{t+ p}{2}\right\rfloor$。

所以 $f(i,j,k,p)$ 往后转移的状态应该是

$$f(i+1,j+t,k+(t+p)\bmod2,\left\lfloor\frac{t+ p}{2}\right\rfloor)$$

由于乘积之和的形式满足乘法分配律，所以不难想到 $f(i,j,k,p)$ 对新状态的贡献应该是

$$f(i,j,k,p)\times v_i^t\times\binom{n-j}{t}$$

初始化 $f(0,0,0,0)=1$。

如何统计答案呢？对于 $i$ 这一维，由于 $a$ 中元素的范围是 $0\sim m$，所以 $S$ 只用看总共 $m+1$ 位，所以是 $m+1$。对于 $j$ 这一维，最终 $n$ 个元素都要确定，所以是 $n$。对于 $k$ 这一维，应该是在 $0\sim k$ 之间的（后面这个 $k$ 是输入的 $k$）。$p$ 这一维就随便了。

不过有一个小细节，就是在 $S$ 的第 $m$ 位有可能还要往后面进位，所以可以使用一个 $\mathrm{popcnt}(p)$ 的函数快速统计出进完位后第 $m$ 位往后的 $1$ 的个数，再加上 $k$ 这一维的数量，如果小于等于输入的 $k$，就可以统计进答案。

$\mathrm{popcnt}$ 函数很简单，就是一直 res += x & 1, x >>= 1 就行了，道理跟前面转移的时候是一样的。

注意还要预处理每个 $v$ 的幂次方结果以及组合数，代码过程中的取模问题等。

这道题还可以用滚动数组进行空间优化，不过我懒。

时间复杂度：$\mathcal{O}(n^4m)$

$\texttt{Code}$

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 998244353;

ll ans, v[105], dp[105][35][35][16], pv[105][35];

ll C[35][35];
inline void init(int n) {
	for (int i = 0; i <= n; i++) C[i][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}

inline int popcnt(int n) {
	int res = 0;
	while (n) res += n & 1, n >>= 1;
	return res;
}

int main() {
	init(30);
	int n, m, K;
	scanf("%d %d %d", &n, &m, &K);
	for (int i = 0; i <= m; i++) {
		scanf("%lld", &v[i]);
		pv[i][0] = 1;
		for (int j = 1; j <= n; j++) pv[i][j] = pv[i][j - 1] * v[i] % mod;
	}
	dp[0][0][0][0] = 1;
	for (int i = 0; i <= m; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= K; k++)
				for (int p = 0; p <= n >> 1; p++)
					for (int t = 0; t <= n - j; t++) dp[i + 1][j + t][k + (t + p & 1)][t + p >> 1] = (dp[i + 1][j + t][k + (t + p & 1)][t + p >> 1] + dp[i][j][k][p] * pv[i][t] % mod * C[n - j][t] % mod) % mod;
	for (int k = 0; k <= K; k++)
		for (int p = 0; p <= n >> 1; p++)
			if (k + popcnt(p) <= K) ans = (ans + dp[m + 1][n][k][p]) % mod;
	printf("%lld", ans);
	return 0;
}