题解 P7223 【[RC-04] 01 背包】

一只书虫仔 · 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;
}