解题思路

给定允许的分段长度集合 {a,b,c}，需要统计长度为 k(1≤k≤n) 的所有切割序列数，且不允许出现相邻片段为“a 后紧跟 c”的情形。顺序不同视为不同方案，答案对 MOD=1e9+7 取模。

核心算法：线性 DP（按最后一段分类）

为了表达“不能出现 a→c 的相邻关系”，只需记住序列最后一段的类型。设：

• dpA[k]：和为 k、且最后一段长度为 a 的方案数
• dpB[k]：和为 k、且最后一段长度为 b 的方案数
• dpC[k]：和为 k、且最后一段长度为 c 的方案数
• tot[k] = dpA[k]+dpB[k]+dpC[k] 为总方案数
• 令空序列 tot[0]=1 仅用于转移（表示“之前什么也没有”），而 dpA[0]=dpB[0]=dpC[0]=0

转移（当下标 <0 时视为 0）：

• 末尾放 a：前面可以接任意结尾或为空 dpA[k] = tot[k-a]
• 末尾放 b：同理 dpB[k] = tot[k-b]
• 末尾放 c：前一段不能是 a，但可以是 b、c 或“空” dpC[k] = tot[k-c] - dpA[k-c]

最后 tot[k] = (dpA[k] + dpB[k] + dpC[k]) % MOD。 特别地，k=c 时，dpC[c] = tot[0] - dpA[0] = 1，自然包含“整段为 c”的方案；k=a、k=b 同理。

由于题目要求输出每个 k=1..n 的结果，我们自底向上线性计算即可，整体 O(n)。

校验示例（a=1,b=2,c=3）： k=4 时，无约束共有 7 种，但 a→c（即 1,3）被禁，DP 给出 6，吻合样例。

复杂度分析

• 时间复杂度：对每组数据线性扫 k=1..n，每个 k 常数次转移，O(n)。题设保证所有测试的 ∑n ≤ 10^6，总时间可控。
• 空间复杂度：需要若干长度为 n+1 的数组，O(n)。若需极限优化，可将三个 dp 与 tot 保留为整型数组，仍在可承受范围内。

代码实现

Python

# -*- coding: utf-8 -*-
# 线性DP，跟踪最后一段类型；禁止 a 后直接跟 c
import sys

MOD = 10**9 + 7

def solve_case(n, a, b, c):
    # 使用整型数组保存 dp 和总数
    dpA = [0] * (n + 1)
    dpB = [0] * (n + 1)
    dpC = [0] * (n + 1)
    tot = [0] * (n + 1)
    tot[0] = 1  # 空序列，仅用于转移

    for k in range(1, n + 1):
        valA = tot[k - a] if k >= a else 0
        valB = tot[k - b] if k >= b else 0
        valC = 0
        if k >= c:
            tmp = tot[k - c] - dpA[k - c]  # 不能从 A 转到 C
            valC = tmp % MOD  # 注意取模避免负值
        dpA[k] = valA % MOD
        dpB[k] = valB % MOD
        dpC[k] = valC
        tot[k] = (dpA[k] + dpB[k] + dpC[k]) % MOD

    # 输出 k=1..n 的 tot[k]
    return tot

def main():
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)
    T = next(it)
    out_lines = []
    for _ in range(T):
        n = next(it); a = next(it); b = next(it); c = next(it)
        tot = solve_case(n, a, b, c)
        out_lines.append(" ".join(str(tot[k]) for k in range(1, n + 1)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 线性DP：按最后一段分类，禁止 a->c 相邻
// 类名必须为 Main（ACM 风格）
import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;

    // 处理单组数据，返回 tot 数组
    static int[] solveCase(int n, int a, int b, int c) {
        int[] dpA = new int[n + 1];
        int[] dpB = new int[n + 1];
        int[] dpC = new int[n + 1];
        int[] tot = new int[n + 1];
        tot[0] = 1; // 空序列，仅用于转移

        for (int k = 1; k <= n; k++) {
            long valA = 0, valB = 0, valC = 0;
            if (k >= a) valA = tot[k - a];
            if (k >= b) valB = tot[k - b];
            if (k >= c) {
                long tmp = (tot[k - c] - (long)dpA[k - c]) % MOD; // 禁止 a->c
                if (tmp < 0) tmp += MOD;
                valC = tmp;
            }
            dpA[k] = (int)(valA % MOD);
            dpB[k] = (int)(valB % MOD);
            dpC[k] = (int)(valC % MOD);
            long sum = (dpA[k] + 0L + dpB[k] + dpC[k]) % MOD;
            tot[k] = (int)sum;
        }
        return tot;
    }

    // 为数据规模考虑，使用 BufferedInputStream + 简易解析
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' '); // 跳过空白
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = fs.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int n = fs.nextInt();
            int a = fs.nextInt();
            int b = fs.nextInt();
            int c = fs.nextInt();
            int[] tot = solveCase(n, a, b, c);
            for (int k = 1; k <= n; k++) {
                if (k > 1) sb.append(' ');
                sb.append(tot[k]);
            }
            sb.append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 线性DP，按最后一段分类；禁止相邻 a->c
// ACM 风格主函数，快速 IO
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

static inline int addmod(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
static inline int submod(int a, int b){ a -= b; if(a < 0) a += MOD; return a; }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if(!(cin >> T)) return 0;
    while(T--){
        int n, a, b, c;
        cin >> n >> a >> b >> c;
        vector<int> dpA(n+1, 0), dpB(n+1, 0), dpC(n+1, 0), tot(n+1, 0);
        tot[0] = 1; // 空序列，仅用于转移

        for(int k = 1; k <= n; ++k){
            int valA = (k >= a) ? tot[k - a] : 0;
            int valB = (k >= b) ? tot[k - b] : 0;
            int valC = 0;
            if(k >= c){
                // 不能从 A 转到 C
                valC = submod(tot[k - c], dpA[k - c]);
            }
            dpA[k] = valA;
            dpB[k] = valB;
            dpC[k] = valC;
            int s = dpA[k];
            s = addmod(s, dpB[k]);
            s = addmod(s, dpC[k]);
            tot[k] = s;
        }

        for(int k = 1; k <= n; ++k){
            if(k > 1) cout << ' ';
            cout << tot[k];
        }
        cout << '\n';
    }
    return 0;
}

本题为2025年9月29日小红书机考原题

小红书机考的介绍点击这里

题目内容

在小红书“品牌创意工坊”中，营销人员可以为直播和短视频活动创建定制化丝带AR特效，结合品牌 $ID$ 与礼盒包装场景，实现动态丝带动画。为了支撑亿级日活的前端渲染，后端需要在活动发布时预先计算并缓存所有可能的切割方案数，确保小程序组件和 $Web$ 端秒级响应。

现有一根虚拟丝带长度为 $k$ ，可以将其分割成若干段或保持一整段不动，但是每段长度只能取整数 $a、b$ 或 $c$ 中的一个，且不允许任何长度为 $a$ 的段后面直接跟随长度为 $c$ 的段。

请对所有长度 $k(1≤k≤n)$ ，统计合法的切割方案数，供小红书前端组件批量加载与渲染。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。顺序不同视为不同方案。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10)$ 代表数据组数，每组测试数据描述如下：

在一行上输入四个整数 $n,a,b,c(1≤n,a,b,c≤10^6)$ ,代表最大丝带长度、可选分段长度 $a,b,c$ 。保证 $a,b,c$ 两两互不相等。

除此之外，保证单个测试文件的 $n$ 之和不超过 $10^6$ 。

输出描述

对于每组测试数据，新起一行,输出 $n$ 个整数，其中第 $k$ 个数表示长度为 $k$ 的丝带的合法分割方案数对 $10^9+7$ 取模的结果。

样例1

输入

2
5 1 2 3
4 1 2 3

输出

1 2 4 6 11
1 2 4 6

说明

在第一个样例中，当 $n=5,a=1,b=2,c=3$ 时：

• $k=1$ 时，仅有一种分割方案 {$1$} ；

• $k=2$ 时，有 {$1,1$} 和 {$2$} 两种方案；

• $k=3$ 时，有 {$1,1,1$},{$1,2$},{$2,1$},{$3$} 共 $4$ 种方案；

• $k=4$ 时，按不带约束的方式共有 $7$ 种方案，但其中 {$1,3$} 不合法，故为 $6$ 种；