这是我打了十多次比赛第一次打到T2的

题目链接: https://www.luogu.com.cn/problem/T157098?contestId=28173

样例能过 但是0pts

思路是枚举全子集然后按题意

My code:

#include <iostream>
#define int long long
using namespace std;
const int maxn = 1e6+10;
const int mod = 998244353;
int a[maxn], n, p, ans;


int quickpower2(int a, int n) {
	if(n==0) return 1;
	if(a==0) return 0;
    int ans = 1;
    while (n) {
        if (n & 1) ans *= a;
        a = a * a;
        n >>= 1;
    }
    return ans;
}

void printBinarySet(int S) {
	int all_things_we = 0;
    for (int i = 0; i < n; i++) {
        if (S & (1 << i)) all_things_we += a[i];
    }
    int tmp = quickpower2(p, all_things_we);
    ans= (ans+tmp)%mod;
}
void printSubsetByBinary() {
    for (int i = 0; i < (1 << n); i++) {
        printBinarySet(i);
    }
}

signed main() {
	cin >> n >> p;
	if(p==0) return 1;
	for(int i=0;i<n;i++) cin >> a[i];
	printSubsetByBinary();
	cout << ans%mod;
	return 0;
}

如果看不到题面, 请:

有一个容积为 $+\infty$ 的背包，你要往里面放物品。

你有 $n$ 个物品，第 $i$ 个体积为 $a_i$

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

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