洛谷 P1164 小 A 点菜

// P1164 小 A 点菜 —— ★ 这一版就能 AC
//
// 题意：N 道菜（每道只有一份），价格 a[i]；恰好把 M 元**花光**，问有多少种点法。
//
// ★ 关键的一步：把 01 背包的 max 换成加法。
//   [第 23 章第 ⑫ 步](/ch/23-knapsack-01/)讲过这个套路 ——
//   问「最大价值」就 max，问「有多少种方案」就把 max 换成 `+`，
//   而初始化从「f 全 0」换成 **f[0] = 1，其余 0**。
//
//   f[j] = 恰好花掉 j 元的点法数
//   f[j] += f[j - a[i]]        （倒序，每道菜只有一份）
//   f[0] = 1                   ← 「一分钱不花」也是一种点法（什么都不点）
//
// ⚠ 那个 f[0] = 1 不是凑数：整张表的方案数都是从它一层层长出来的。
//   忘了它，全表恒为 0（见 p1164Zero.cpp）。
//
// ★ 关于 int 够不够：题面写着「保证答案在 [0, 2^31-1] 之内」——
//   这句话**正好是 int 够用的充分条件**，而且能证（解析页第 ⑤ 步）。
//   ⚠ 但「用得上的格子不溢出」不等于「所有格子都不溢出」，所以这里仍写 long long。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;            // ⚠ 顺序是「菜品种类 N，钱数 M」
    vector<long long> f(m + 1, 0);
    f[0] = 1;                                  // ★ 一分钱不花：一种点法

    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        for (int j = m; j >= a; j--)           // 倒序：每道菜只有一份
            f[j] += f[j - a];
    }
    cout << f[m] << "\n";
    return 0;
}

// P1164 错法四：把两个输入读反了 —— ★★ 而官方样例**在结构上问不出这个问题**
//
// 题面第一行是「N 和 M」＝「菜品种类、身上的钱」。
// 而「先读钱、再读个数」也很顺手（很多背包题的输入就是那个顺序），于是有了这一版。
//
// ★★★ 官方样例是 `4 4` —— **N 和 M 恰好相等**，交换它们是**恒等变换**。
//   ⇒ 这不是「概率低」，是**精确的 0**：这组样例问不出这个问题。
//     和[第 14 章 P1746](/sol/p1746/) 那个「两个点都在主对角线上」是同一件事。
//
// ⚠ 而读反之后还会再错一次：菜价那一行要读 N 个数，读成 M 个就会读少 / 读多。
//   这里如实照抄「读反了」的写法：n 和 m 换个位置，别的一个字不改。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    if (!(cin >> m >> n)) return 0;            // ⚠ 反了：先读的其实是 N
    vector<long long> f(m + 1, 0);
    f[0] = 1;
    for (int i = 0; i < n; i++) {
        int a = 0;
        if (!(cin >> a)) break;                // 读不到就算了（数量对不上）
        for (int j = m; j >= a; j--)
            f[j] += f[j - a];
    }
    cout << f[m] << "\n";
    return 0;
}