#P4428. 26秋招-小红书笔试-小红书丝带AR特效
-
1000ms
Tried: 1
Accepted: 1
Difficulty: 4
26秋招-小红书笔试-小红书丝带AR特效
解题思路
给定允许的分段长度集合 {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) ,统计合法的切割方案数,供小红书前端组件批量加载与渲染。由于答案可能很大,请将答案对 (109+7) 取模后输出。顺序不同视为不同方案。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤10) 代表数据组数,每组测试数据描述如下:
在一行上输入四个整数 n,a,b,c(1≤n,a,b,c≤106) ,代表最大丝带长度、可选分段长度 a,b,c 。保证 a,b,c 两两互不相等。
除此之外,保证单个测试文件的 n 之和不超过 106 。
输出描述
对于每组测试数据,新起一行,输出 n 个整数,其中第 k 个数表示长度为 k 的丝带的合法分割方案数对 109+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 种;