F - Knapsack for All Subsets 子集和=s 问题

以下是官解的翻译。
还是挺抽象的。这题的代码非常简单。但是我逛了几乎所有的题解 都没有给与明确的逻辑说明。

这个问题可以概括如下：有多少对集合(T, U)满足以下条件？T和U都是{1, 2, …, N}的非空子集，并且:

U是T的子集
设U = {x1, x2, …, xk}，则ax1 + ax2 + … + axk = S

然后，对于每个i (1 ≤ i ≤ n)，有三种选择:

同时放入U和T
放入T，但不放入U
既不放入U也不放入T

只有当选择第一个选项时，和才会增加ai。
根据上述观察，可以看出使用动态规划和以下递归关系可以解决这个问题:
dp[i][j] = 当前i个选项的选择已经确定时，使得所有选择第一个选项的k的ak之和等于j的组合数。
所需的答案是dp[N][S]，总时间复杂度为O(NS)。

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : for j in range(S + 1) : dp[i + 1][j] += 2 * dp[i][j]dp[i + 1][j] %= mod if j + A[i] <= S : dp[i + 1][j + A[i]] += dp[i][j]dp[i + 1][j + A[i]] %= mod
print(dp[N][S])