P3544.第2题-品牌创意工坊
题目内容
在小红书“品牌创意工坊”中，营销人员可以为直播和短视频活动创建定制化丝带AR特效，结合品牌ID与礼盒包装场景，实现动态丝带动画。为了支撑亿级日活的前端渲染，后端需要在活动发布时预先计算并缓存所有可能的切割方案数，确保小程序组件和Web端秒级响应。
现有一根虚拟丝带长度为k，可以将其分割成若干段或保持一整段不动，但是每段长度只能取整数a、b或c中的一个，且不允许任何长度为a的段后面直接跟随长度为c的段。
请对所有长度k(1≤k≤n) ，统计合法的切割方案数，供小红书前端组件批量加载与渲染。由于答案可能很大，
请将答案对(109+7)取模后输出。顺序不同视为不同方案。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤104)代表数据组数，每组测试数据描述如下:
在一行上输入四个整数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种;
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
