算法
(01背包、生成函数) $O(NS)$
记 dp[i][j]
表示以 $A_i$ 结尾的子序列中构成和为 $j$ 的子序列个数
状态转移:
dp[i + 1][j + A[i]] += dp[i][j]
dp[i + 1][j] += dp[i][j]
不难看出上面的 dp
是个 01
背包,我们可以也可以用生成函数来处理
比如:
2 4 2
s=4
对于每个数可以选,也可以不选,所以有两种状态,也就是 $1 + x^{A_i}$
所以由这个例子可以得到多项式 $f = (1 + x^2)(1 + x^4)(x + x^2)$
展开后,我们可以得到 $f = x^8 + 2x^6 + 2x^4 + 2x^2 + 1$
这里的 $x^4$ 的系数对应的就是 $dp[4]$
记 $P_1 = 1 + x^2$,$P_2 = 1 + x^4$,$P_3 = 1 + x^2$
原问题可以转化成求
- $P_1$ 的 $x^4$ 的系数
- $P_1P_2$ 的 $x^4$ 的系数
- $P_1P_2P_3$ 的 $x^4$ 的系数
- $P_2$ 的 $x^4$ 的系数
- $P_2P_3$ 的 $x^4$ 的系数
- $P_3$ 的 $x^4$ 的系数
我们可以把左边的多项式直接相加,因为并不会影响求 $x^4$ 的系数
即:$P_1 + P_1P_2 + P_1P_2P_3 + P_2P_3 + P_3 \ (*)$
而这个式子等价于 $P_1(1 + P_2 + P_2P_3) + P_2 + P_2P_3 + P_3$
记 $Q_1 = P_1(1 + P_2 + P_2P_3)$,$Q_2 = P_2 + P_2P_3$,$Q_3 = P_3$
于是,我们可以得到
- $Q_1 = P_1(1+Q_2)$
- $Q_2 = P_2(1+Q_3)$
- $Q_3 = P_3(1+Q_4)$
其中,$Q_4 = 0$
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;
int main() {
int n, s;
cin >> n >> s;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<mint> q(s + 1);
mint ans;
rep(i, n) {
q[0] += 1; // q += 1
{ // q *= (1 + x^a[i])
vector<mint> q2(s + 1);
rep(j, s + 1) {
q2[j] += q[j];
if (j + a[i] <= s) q2[j + a[i]] += q[j];
}
q = q2;
}
ans += q[s];
}
cout << ans.val() << '\n';
return 0;
}