齿轮装配线
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
机械工坊里有一条长度为 的装配轨道,仓库里有 个齿轮,编号为 。
第 个齿轮安装到轨道上会占据恰好 个单位长度。每个齿轮至多安装一次,也可以不安装。
设选中齿轮的编号集合为 。当且仅当
时,选中的齿轮恰好完整铺满整条轨道。
每个齿轮都按编号区分。两种选法不同,当且仅当它们对应的编号集合 不同;即使 ,选择齿轮 与选择齿轮 也视为不同方案。
请计算满足条件的集合 的数量,并对
取模。如果不存在合法选法,答案为 。
输入格式
第一行输入两个整数 (,),分别表示齿轮数量和轨道长度。
第二行输入 个整数 (),表示每个齿轮占用的单位长度。
输出格式
输出一行一个整数,表示满足
的编号集合 的数量对 取模后的结果。
样例
5 5
1 2 3 2 5
4
3 7
2 2 4
0
提示
样例 中,占用长度之和恰好为 的编号集合有
$$\{2,3\},\quad \{3,4\},\quad \{1,2,4\},\quad \{5\},$$共 种。注意,齿轮 与齿轮 的占用长度都是 ,但它们按编号区分,因此 与 是两种不同的选法。
样例 中,任意选法的占用长度之和只可能是 ,不存在恰好等于 的选法,因此答案为 。
第十三届校赛(重现赛+改题)暨2026级SYUCT-ACM新生第三次部分训练暨SYUCTACM周赛#1
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 8
- 开始于
- 2026-10-16 18:30
- 结束于
- 2026-10-16 21:00
- 持续时间
- 2.5 小时
- 主持人
- 参赛人数
- 59