洛谷 P1077 [NOIP 2012 普及组] 摆花

// P1077 [NOIP 2012 普及组] 摆花 —— ★ 这一版就能 AC
//
// 题意：n 种花排成一排共 m 盆，第 i 种不超过 a_i 盆，**同种花放在一起、按标号从小到大摆**。
//       ⇒ 「摆法」其实就是决定「每种花各摆几盆」：`k_1 + k_2 + … + k_n = m`，`0 ≤ k_i ≤ a_i`。
//       求方案数，对 **10⁶ + 7** 取模。
//
// ★ DP 三件套（第 21 章第 ⑤ 步那一套）：
//   · 状态：`f[i][j]` = 前 i 种花一共摆了 j 盆的方案数；
//   · 转移：`f[i][j] = Σ_{k=0..min(a_i, j)} f[i-1][j-k]`（第 i 种摆 k 盆）；
//   · 边界：`f[0][0] = 1`（一种花都没摆、一共 0 盆 —— 这是**一种**方案，不是零种）。
//
// ⚠ 三个和 DP 无关、但每年都有人栽的地方（页面上各量了一个）：
//   ① ★★★ **模数是 `10⁶ + 7 = 1000007`，不是 `10⁹ + 7`** —— 这道题最出名的坑，
//      而它**只在真实答案 ≥ 1000007 时才现形**（页面第 ④ 步把这条线量了出来）；
//   ② `k` 要**从 0 开始**：题面允许某一种花一盆都不摆（`0 ≤ a_i` 也允许某种花上限就是 0）；
//   ③ 不取模一定炸：顶格方案数约 `4.5 × 10⁵⁸`（页面第 ⑤ 步算了这一笔）。
//
// 复杂度 `O(n m max_a)`，顶格 100³ = 10⁶。★ 前缀和还能优化到 `O(nm)`（页面第 ⑥ 步）。

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

const int MOD = 1000007;                     // ★ 10^6 + 7

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
    f[0][0] = 1;                             // ★ 边界
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= min(a[i], j); k++)      // ★ k 从 0 开始
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;

    cout << f[n][m] << "\n";
    return 0;
}

// P1077 的参照物：**直接搜** —— 枚举每种花各摆几盆
//
// ★ 它不需要「状态 / 转移 / 边界」那一套，只把题意照抄一遍：
//   第 i 种花摆 0..a_i 盆，摆完 n 种正好 m 盆就算一种方案。
// ⚠ 只跑得动小数据（题面 20% 那一档 `n, m, a_i ≤ 8` 正好够）——
//   但它是这一页唯一一个**不依赖任何想法**的答案来源。
//
// ★ 它也不取模：小数据上方案数很小，正好用来看「真实答案有多大」
//   （页面第 ④ 步那条数值线就是靠它量的）。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

static int n, m;
static vector<int> a;
static ull ways;

static void dfs(int i, int left) {
    if (i > n) { if (left == 0) ways++; return; }
    for (int k = 0; k <= min(a[i], left); k++) dfs(i + 1, left - k);
}

int main() {
    if (!(cin >> n >> m)) return 0;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    ways = 0;
    dfs(1, m);
    cout << ways % 1000007ULL << "\n";
    return 0;
}

// P1077 错法一：★★★ 模数写成 `10⁹ + 7`
//
// 这是这道题最出名的坑：`10⁹+7` 是竞赛里最常见的模数，手指头比脑子快。
// 而这道题的题面写的是「对 **10⁶ + 7** 取模」。
//
// ★★ 它的触发条件是一条**数值线**：只有当真实方案数 **≥ 1000007** 时，
//   两个模数才可能给出不同的结果 —— 页面第 ④ 步把这条线量成了一张表。
//   ⇒ 小数据上它**一次都不会错**，而官方样例的答案是 **2**。

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

const int MOD = 1000000007;                  // ← 手滑：10^9 + 7

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= min(a[i], j); k++)
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
    cout << f[n][m] << "\n";
    return 0;
}

// P1077 错法二：`k` 从 1 开始 —— 把题面读成了「每种花至少摆一盆」
//
// 题面只说「第 i 种花**不能超过** a_i 盆」，没说至少要摆几盆 ——
// 而且数据范围里写着 `0 ≤ a_i`，也就是**某一种花的上限本身就可能是 0**。
//
// ★★ 而官方样例**放过了它**：`n = 2, m = 4, a = [3, 2]`，
//   两种合法摆法是 `(2,2)` 和 `(3,1)` —— 恰好**每一种花都摆了至少一盆**。
//   ⇒ 又一次「样例只有一组，它挡不住这种偶尔才错的」。

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

const int MOD = 1000007;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 1; k <= min(a[i], j); k++)      // ← 从 1 开始，漏掉「这种花不摆」
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
    cout << f[n][m] << "\n";
    return 0;
}

// P1077 错法三：不取模（用 `unsigned long long` 硬存）
//
// ★ 「要不要取模」这道题**替你决定了** —— 题面直接写着「方案数可能很多，请输出对 10⁶+7 取模的结果」。
//   而这句话背后的数字值得算一遍：顶格 `n = m = 100`、`a_i = 100` 时，
//   方案数就是「`k_1 + … + k_100 = 100`、`0 ≤ k_i ≤ 100`」的解数 = `C(199, 99) ≈ 4.5 × 10⁵⁸`。
//   `unsigned long long` 上限约 `1.8 × 10¹⁹` —— **差 39 个数量级**。
//
// ⚠ 这里故意用 **unsigned** 而不是 long long：无符号溢出是**回绕**（有定义、可复现），
//   有符号溢出是 UB，演示出来的数字下次可能就变了（本书第 51~53 条那组经验）。
//
// ★★ 和同一轮那份 [P1080](/sol/p1080/) 正好凑成一对：
//   那道题**必须写高精度**，因为题面要的就是那个几千位的数；
//   这道题题面**替你把数缩小了** —— **「取模」就是出题人发的「不用写高精度」的许可**。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<unsigned long long>> f(n + 1, vector<unsigned long long>(m + 1, 0));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= min(a[i], j); k++)
                f[i][j] += f[i - 1][j - k];              // ← 一次都不取模
    cout << f[n][m] % 1000007ULL << "\n";                // 最后才补一次，已经晚了
    return 0;
}

// P1077 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1077Count`      人看的版本
// `./p1077Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 六段：
//   ① ★ DP ≡ 直接搜（题面「20% 的数据」那一档）；
//   ② ★★★ **模数写成 10⁹+7 那个错法的数值线**：只有真实方案数 ≥ 1000007 时才可能露馅 ——
//      算出最小的 `n = m`，再实测「被抓的轮数」和「越线的轮数」对不对得上；
//   ③ ★★ 「k 从 1 开始」（读成「每种花至少一盆」）的抓获率和它的触发条件；
//   ④ ★★★ **不取模会怎样**：顶格方案数有多大（和 unsigned long long 上限比），
//      以及最小的会溢出的 `n = m`；
//   ⑤ ★ 前缀和优化：`O(n m max_a)` → `O(n m)`，用**加法次数**这把机器无关的尺子量；
//   ⑥ ★ 官方样例：四个版本各输出什么（⚠ 三个错法**一个都没挡住**）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

struct In { int n, m; vector<int> a; };

/** 正解：三重循环 DP。cnt 记加法次数（机器无关的尺子） */
static int dp(const In& in, ll mod, int kFrom = 0, ll* cnt = nullptr) {
    vector<vector<ll>> f(in.n + 1, vector<ll>(in.m + 1, 0));
    f[0][0] = 1;
    for (int i = 1; i <= in.n; i++)
        for (int j = 0; j <= in.m; j++)
            for (int k = kFrom; k <= min(in.a[i], j); k++) {
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % mod;
                if (cnt) (*cnt)++;
            }
    return (int)f[in.n][in.m];
}
/** 前缀和优化：O(n m)。cnt 同样记加法次数 */
static int dpPrefix(const In& in, ll mod, ll* cnt = nullptr) {
    vector<ll> f(in.m + 1, 0), g(in.m + 1, 0), s(in.m + 2, 0);
    f[0] = 1;
    for (int i = 1; i <= in.n; i++) {
        s[0] = 0;
        for (int j = 0; j <= in.m; j++) { s[j + 1] = (s[j] + f[j]) % mod; if (cnt) (*cnt)++; }
        for (int j = 0; j <= in.m; j++) {
            int lo = max(0, j - in.a[i]);
            g[j] = ((s[j + 1] - s[lo]) % mod + mod) % mod;      // f[lo..j] 之和
            if (cnt) (*cnt)++;
        }
        f = g;
    }
    return (int)f[in.m];
}
/** 参照物：直接搜（不取模，用大整数近似不了就退回 ull 回绕，这里只在小数据上用） */
static ull brute(const In& in) {
    ull ways = 0;
    function<void(int, int)> dfs = [&](int i, int left) {
        if (i > in.n) { if (left == 0) ways++; return; }
        for (int k = 0; k <= min(in.a[i], left); k++) dfs(i + 1, left - k);
    };
    dfs(1, in.m);
    return ways;
}
/** 真实方案数（不取模）—— 用 long double 估个量级，够判「有没有越过某条线」 */
static long double exactApprox(const In& in) {
    vector<long double> f(in.m + 1, 0.0L);
    f[0] = 1;
    for (int i = 1; i <= in.n; i++) {
        vector<long double> g(in.m + 1, 0.0L);
        for (int j = 0; j <= in.m; j++)
            for (int k = 0; k <= min(in.a[i], j); k++) g[j] += f[j - k];
        f = g;
    }
    return f[in.m];
}

static In gen(mt19937& rng, int hi, int aHi) {
    In in;
    in.n = (int)(rng() % (unsigned)hi) + 1;
    in.m = (int)(rng() % (unsigned)hi) + 1;
    in.a.assign(in.n + 1, 0);
    for (int i = 1; i <= in.n; i++) in.a[i] = (int)(rng() % (unsigned)(aHi + 1));
    return in;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";
    const ll SMALL = 1000007, BIG = 1000000007;

    /* ① DP ≡ 直接搜 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            In in = gen(rng, 8, 8);
            if ((ull)dp(in, SMALL) != brute(in) % (ull)SMALL) bad++;
        }
        if (!CSV) printf("① 题面 20%% 那一档（n, m, a ≤ 8）：DP vs 直接搜 %d 组，不一致 %d 组\n", groups, bad);
        row("ref", {groups, bad});
    }

    /* ② 模数写成 10^9+7：先算那条线，再实测 */
    {
        // 算：n = m = k、a_i = k 时方案数 = C(2k-1, k-1)，找最小的 ≥ 1000007 的 k
        int lineK = -1;
        long double c = 1;
        for (int k = 1; k <= 60; k++) {
            long double v = 1;                       // C(2k-1, k-1)
            for (int t = 1; t <= k - 1; t++) v = v * (k + t) / t;
            if (v >= 1000007.0L) { lineK = k; c = v; break; }
        }
        if (!CSV) printf("② 算出来的线：n = m = a = %d 时方案数 C(%d, %d) ≈ %.0Lf ≥ 1000007\n",
                         lineK, 2 * lineK - 1, lineK - 1, c);
        // 实测三档：题面 20% 档 / 中档 / 顶格
        const int HIS[] = {8, 20, 100};
        vector<ll> out = {lineK};
        for (int hi : HIS) {
            mt19937 rng(hi * 7919u + 3u);
            int caught = 0, over = 0;
            for (int r = 0; r < 200; r++) {
                In in = gen(rng, hi, hi);
                // ⚠ 评测比的是**原样输出**，所以这里直接比两个版本打出来的数
                if (dp(in, SMALL) != dp(in, BIG)) caught++;
                if (exactApprox(in) >= 1000007.0L) over++;
            }
            out.push_back(caught); out.push_back(over);
            if (!CSV) printf("② n, m, a ≤ %3d（200 轮）：模数写成 10^9+7 被抓 %d 次；"
                             "真实方案数 ≥ 1000007 的有 %d 轮\n", hi, caught, over);
        }
        row("bigmod", out);
    }

    /* ③ k 从 1 开始 */
    {
        const int HIS[] = {8, 20, 100};
        vector<ll> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 40503u + 11u);
            int bad = 0, hasZero = 0;
            for (int r = 0; r < 200; r++) {
                In in = gen(rng, hi, hi);
                if (dp(in, SMALL, 1) != dp(in, SMALL, 0)) bad++;
                // 触发条件：存在「某种花摆 0 盆」的合法方案 ⇔ 去掉任意一种花之后仍能摆满
                bool z = false;
                for (int i = 1; i <= in.n && !z; i++) {
                    In sub = in;
                    sub.a[i] = 0;
                    if (dp(sub, SMALL) != 0) z = true;
                }
                if (z) hasZero++;
            }
            out.push_back(bad); out.push_back(hasZero);
            if (!CSV) printf("③ n, m, a ≤ %3d（200 轮）：k 从 1 开始那版错 %d 次；"
                             "存在「某种花摆 0 盆」的方案的有 %d 轮\n", hi, bad, hasZero);
        }
        row("from1", out);
    }

    /* ④ 不取模会怎样 */
    {
        // 顶格 n = m = a = 100：方案数 = C(199, 99)
        long double v = 1;
        for (int t = 1; t <= 99; t++) v = v * (100 + t) / t;
        // 最小的会超过 2^64 的 n = m = a = k
        int k64 = -1;
        for (int k = 1; k <= 200; k++) {
            long double w = 1;
            for (int t = 1; t <= k - 1; t++) w = w * (k + t) / t;
            if (w >= 18446744073709551616.0L) { k64 = k; break; }
        }
        ll digits = (ll)floorl(log10l(v)) + 1;
        if (!CSV) printf("④ 顶格 n = m = a = 100：方案数 C(199, 99) ≈ 4.5e%lld（%lld 位），"
                         "unsigned long long 上限约 1.8e19 ⇒ 最小会溢出的 n = m = a 是 %d\n",
                         digits - 1, digits, k64);
        row("nomod", {digits, k64, 20});
    }

    /* ⑤ 前缀和优化：数加法次数 */
    {
        const int KS[] = {20, 50, 100};
        vector<ll> out;
        for (int k : KS) {
            In in;
            in.n = k; in.m = k;
            in.a.assign(k + 1, k);
            ll c1 = 0, c2 = 0;
            int r1 = dp(in, SMALL, 0, &c1), r2 = dpPrefix(in, SMALL, &c2);
            out.push_back(c1); out.push_back(c2); out.push_back(r1 == r2 ? 1 : 0);
            if (!CSV) printf("⑤ n = m = a = %3d：三重循环加了 %lld 次，前缀和版 %lld 次"
                             "（少 %.1f 倍），答案%s\n", k, c1, c2, (double)c1 / c2,
                             r1 == r2 ? "相同" : "**不同**");
        }
        row("prefix", out);
    }

    /* ⑥ 官方样例 */
    {
        In in;
        in.n = 2; in.m = 4; in.a = {0, 3, 2};
        int ok = dp(in, SMALL), big = dp(in, BIG), from1 = dp(in, SMALL, 1);
        if (!CSV) printf("⑥ 官方样例：正解 %d、模数写错 %d、k 从 1 开始 %d ——"
                         " ⚠ 三个错法**一个都没挡住**\n", ok, big, from1);
        row("sample", {ok, big, from1});
    }
    return 0;
}

// P1077 对拍生成器：`./p1077Gen <seed> [n、m 的上限] [a 的上限]`
//   默认 `n, m ≤ 8`、`a_i ≤ 8` —— ★ **就是题面里「对于 20% 的数据」那一档**，
//   小到可以用「直接搜」当参照物。
//
// ★ 而这一页最要紧的旋钮是**规模**，因为「模数写成 10⁹+7」那个错法有一条**数值线**：
//   只有真实方案数 ≥ 1000007 时它才可能露馅。
//   照题面 20% 那档随机，方案数顶多几百 ⇒ **它一次都不会被抓**（页面第 ④ 步那张表）。
//   ⇒ 这一档验的是「DP 写对没有」，验不了「模数抄对没有」——
//     和同一轮 [P1080](/sol/p1080/) 那条一模一样：**一半靠对拍，一半只能靠算。**

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int hi = argc > 2 ? atoi(argv[2]) : 8;
    int aHi = argc > 3 ? atoi(argv[3]) : 8;
    hi = max(1, min(100, hi));
    aHi = max(0, min(100, aHi));

    mt19937 rng(seed * 2654435761u + 77u);
    int n = (int)(rng() % (unsigned)hi) + 1;
    int m = (int)(rng() % (unsigned)hi) + 1;
    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++)
        printf("%u%c", (unsigned)(rng() % (unsigned)(aHi + 1)), i + 1 == n ? '\n' : ' ');
    return 0;
}