[RC-04] 0 1 背包

[RC-04] 01 背包

 题目描述

有一个容积为无穷的背包，你要往里面放物品。

你有 n个物品，第 i 个体积为 ai。

你有一个幸运数字 p，若放入的物品体积和为 k，你会得到 p^k$的收益。特别地，0^0=1。

求所有 2^n 种放入物品的方案的收益和。答案很大，因此请输出它对 $998244353$ 取模的值。

 输入格式

第一行两个整数 n,p。

接下来一行 n 个正整数 a1~an，描述这 n 个物品的体积。

## 输出格式

输出一个整数，为所有 2^n 种方案的收益和对 998244353 取模的值。

 样例输入 1

```
2 2
1 4
```

样例输出 1

```
51
```

//对于第i个物品都有两个选择 ,选择，则它的贡献就是乘上p^ai；不选，则它的贡献就是1

经过总结得

答案为 (p^a1+1)*(p^a2+1)*(p^a3+1)*(p^a4+1)*(p^a5+1)*……(p^an+1)

在求p^ai%mod时，可以使用快速幂进行计算

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=998244353;
int qmi(int a,int k,int p)   //快速幂
{
    int ans=1;
    while (k)
    {
        if (k&1) ans=ans*a%p;
        k >>=1;
        a=a*a%p;
    }
    return ans;
}
signed main()
{
    int n,p;
    cin>>n>>p;
    int sum=1;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum=sum*(qmi(p,x,mod)+1)%mod;    //公式
    }
    cout<<sum;
    return 0;
}