如果我们定义\(dp[i][j]\)表示对于前i个字符而言，其子集满足条件的个数。那4么对于一个位置i而言，要么选择它贡献要么不选择，所以
\(dp[i][j] = dp[i - 1][j - a[i]](j >= a[i]) + dp[i - 1][j]\)，这是每一个\(f(i)\)的函数。
然后我们加上所有的\(dp[i][k](i : 1 到 n)ans += dp[i][k]\)
似乎\(ans\)就是答案。但是这样显然是有问题的。因为我们求的\(S\)的子集，而这里我们只求了\(S\)所有的前缀的\(f\)函数之和。
那么我们考虑对于一个\(S\)的子集，它的大小是\(siz\)，而且满足其中元素的和是\(k\)，那么它对全局\(S\)的贡献是\(2^{n-siz}\)，因为如果这个子集的贡献增加1，就代表必须选完这\(siz\)个元素，其它的选择或者不选择。这样将元素加起来就会构成一个新的集合，这个方案数就是\(2^{n - siz}\)。
但是如何运用\(dp\)进行计算呢？这里我有一个固定的思维，就是我给了\(i\)两个限制，一个是子集的子集上的，一个是子集上的。意思是说，\(T\)是\(S\)的子集，\(X\)是\(T\)的子集，我找到了满足条件的\(X\)，其中\(X\)是从前\(i\)个字符中选择的。在我的上一个\(dp\)中，这样的\(X\)的贡献只会给连续的前\(i\)个的S的子集T。
Ca都觉得自己没说的很清楚。总而言之就是，我们i的限制仅仅只是对于前i个子集而言的，我们的贡献是在全局上的。\(dp[i][j]\)表示选择\(X\)子集，\(X\)在前\(i\)中选择，对于所有的\(X\)而言，对所有的\(T\)的贡献的总和。也就是在前\(i\)个元素中选择子集，全局中所有\(f(T)\)（含有子集价值之和为j）之和的答案。
初始化是\(dp[0][0] = 2 ^ n\), 全局\(2 ^ n\)个子集都是含有空集，但是显然我们在后面选的时候是不能为空集的，这里也提示了为什么/2
\(dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]] /div 2\)
首先要加上我们之前已经算好了可以贡献j个的，然后我们在i - 1个元素之前计算\(f(j - a[i])\)的时候，既然已经减少了，就代表这个元素一定是要选择的，那么我们在计算\(f(j - a[i])\)的时候，对i这个位置肯定是没有任何限制的，但是我们现在必须选，所以对全局的贡献就会在之前的基础上少一半，少的是我满足和是\(j - a[i]\)但是我没有选择\(a[i]\)的方案。
到了这里ca就有一种感觉，\(dp[0][0]\)表示我最开始所有的方案数都是满足条件的，但是我在对和有了要求，于是这个位置就会产生选择或者不选则的要求，于是我们的答案就会有\(\div 2\)的变化。
神奇体验。Qwq
- 菜就多练。
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
typedef long long ll;
const int mod = 998244353;
int dp[N][N], n, k, a[N], ans = 0, yyz;
int q_pow(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1) res = (ll)res * a % mod;
a = (ll)a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
dp[0][0] = q_pow(2, n);
yyz = q_pow(2, mod - 2);
for (int i = 1; i <= n; ++ i)
{
for (int j = 0; j <= k; ++ j)
{
if(j >= a[i]) dp[i][j] = (ll)dp[i - 1][j - a[i]] * yyz % mod;
dp[i][j] = (ll)(dp[i][j] + dp[i - 1][j]) % mod;
}
}
printf("%lld", (ll)(dp[n][k] + mod) % mod);//好习惯
}