题解：T496174 「金坷垃杯 R1」十三太保

出题人官方题解～

---

其实这种计数问题无非就 种方法：

1. 爆搜，dfs 枚举所有情况
2. 数学方法，计算
3. dp

显然这题不让你搜，数学方法又没有，那就只能 dp 了。

---

然后来看题。数列中每个数字只能选择一次，因此抽象过来就是这样的：

01 背包问题，求正好能选数选成 的方案数。

这不就是板题了吗……

按照 “题目问什么，状态设什么” 的状态定义原则，定义 前 个数中选数使和正好为 的方法数。转移也很显然，是 。

注意要用滚动数组优化，不然就是 MLE。

---

std:

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e7 + 10;
int k, n, a[N], dp[N];

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	if (x < 0) {
		putchar('-'), write<T>(-x);
		return;
	}
	static T sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

int main() {
	cin >> n >> k;
	FOR(i, 1, n) cin >> a[i];
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = k; j >= 0;j--) dp[j] += dp[j - a[i]];
	cout << dp[k] << endl;
	return 0;
}