1 条题解

  • 0
    @ 2026-11-12 21:57:42

    [M] Candies(dp_m)题解

    题意简述

    NN 个孩子,第 ii 个分到 0∼ai0 \sim a_i 个糖,总数恰好为 KK,求方案数  mod 109+7\bmod 10^9+7。

    思路

    朴素 DP

    fi,xf_{i,x} = 前 ii 个孩子共分 xx 个糖的方案数:

    $$f_{i,x} = \sum_{y = \max(0,\,x-a_i)}^{x} f_{i-1,\,y}.$$

    朴素转移 O(K)O(K),总计 O(NK2)O(NK^2) 会超时。

    前缀和优化

    固定 ii 后,fi,xf_{i,x} 是 fi−1f_{i-1} 的一段滑动窗口和:

    $$f_{i,x} = \text{pre}_{i-1}[x] - \text{pre}_{i-1}[\max(0, x-a_i) - 1],$$

    其中 prei−1[t]=∑y≤tfi−1,y\text{pre}_{i-1}[t] = \sum_{y \le t} f_{i-1,y}。于是每层 O(K)O(K),总计 O(NK)O(NK)。

    为什么正确

    转移区间 [max⁡(0,x−ai),x][\max(0,x-a_i), x] 的左右端点都随 xx 单调右移,用前缀和差即可 O(1)O(1) 得到区间和。转移只依赖上一层,倒序原地更新(或滚动数组)都安全。

    复杂度

    时间 O(NK)≤107O(NK) \le 10^7,空间 O(K)O(K)。

    参考代码

    #include <cstdio>
    #include <vector>
    using namespace std;
    
    const long long MOD = 1000000007LL;
    
    int main() {
        int n, k;
        scanf("%d %d", &n, &k);
        vector<long long> f(k + 1, 0), pre(k + 1, 0);
        f[0] = 1;
        for (int i = 0; i < n; i++) {
            int a;
            scanf("%d", &a);
            pre[0] = f[0];
            for (int x = 1; x <= k; x++) pre[x] = (pre[x - 1] + f[x]) % MOD;
            for (int x = k; x >= 0; x--) {
                int lo = x - a;
                f[x] = (pre[x] - (lo > 0 ? pre[lo - 1] : 0) + MOD) % MOD;
            }
        }
        printf("%lld\n", f[k]);
        return 0;
    }
    

    易错点

    1. pre 必须在当前层算好再用;若边算 f 边改 pre 就错了(所以先算完整层 pre)。
    2. pre[lo-1] 的下标可能为 00 甚至负,要写成 lo > 0 ? ... : 0。
    3. 取模减法要加 MOD 防负数。
    4. ai=0a_i = 0 与 K=0K = 0 都是合法边界:K=0K=0 时答案为 11(全 0 分配),样例 3 就是。

    数据说明

    共 19 组:4 组官方样例(含 K=0K=0 与答案 665683269665683269);N=1N=1 的 a=0/a=K/a=K/2a=0/a=K/a=K/2;N=2N=2 的 a=0,0a=0,0 与 a=K,Ka=K,K;N=3N=3 全 00;N=100N=100 全 00、全 KK、随机六组。

    • 1

    信息

    ID
    22
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者