自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:27:50，当前版本为作者最后更新于2021-01-02 17:36:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Description

给定 $n$ 个物品，把第 $i$ 个物品放入背包的收益为 $a_i$。
求所有 $2^n$ 种放置方法得到的收益总和。
答案对 $998\ 244\ 353$ 取模。

Solution

对于第 $i$ 个物品：

• 选他，跟他相连的所有方案会 乘上 $p^{a_i}$。
• 不选他，跟他相连的所有方案会 乘上 $1$。

为什么会是乘上呢？比如说我们选择第 $1,4,5$ 个物品，那么会获得的收益是：

$$p^{a_1+a_4+a_5}=p^{a_1} \times p^{a_4} \times p^{a_5} $$

那么没有选择的第 $2,3$ 个物品在这里的贡献就是 $1$。

所以答案为：

$$(p^{a_1}+1)(p^{a_2}+1)\cdots(p^{a_n}+1)=\prod_{i=1}^n(p^{a_i}+1) $$

Code

#include <bits/stdc++.h>
#define Mod 998244353

using namespace std;

long long binpow (long long b, long long p, long long k) {
	b %= k;
	long long res = 1;
	while (p > 0) {
		if (p & 1)
			res = res * b % k;
		b = b * b % k;
		p >>= 1;
	}
	return res;
}

long long a[1000086];

int main () {
	long long n, p;
	long long ans = 1;
	scanf("%lld%lld", &n, &p);
	for (long long i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for (long long i = 1; i <= n; i++) {
		ans *= (binpow(p, a[i], Mod) % Mod + 1);
		ans %= Mod;
	}
	printf("%lld", ans % Mod);
	return 0;
}