#P10331. 攻城带獅
攻城带獅
题目描述
有 座城市,编号为 ,第 座城市有一个正整数收益 。每回合选择一个非空城市集合并攻打,回合收益为所选城市收益的最大公约数。回合结束后城市恢复,整个过程中每个集合最多选择一次。
进行 个回合,使回合收益之和最大。收益相同的方案按以下优先级比较。将两个集合分别按城市编号升序列出,比较第一个不同的位置,该位置编号较小的方案优先。如果一个序列是另一个序列的前缀,较短者优先。满足最大总收益的前提下,优先选取优先级更高的同收益方案。
一个攻击方案的哈希值为其所有城市编号的乘积。求选中的 个方案哈希值之和,对 取模。
输入格式
第一行两个整数 。第二行 个整数 。
输出格式
若不存在 个不同的非空集合,输出 -1。否则输出一行一个整数,表示哈希值之和对 取模的结果。
样例 1
5 10
2 6 3 9 5
67
样例 2
20 10000
18 12 16 20 8 20 2 12 20 2 14 20 14 16 12 8 20 16 14 20
2840199644
原题还在下发文件中提供样例 3。
数据范围
| 测试点 | 上界 | 上界 | 上界 |
|---|---|---|---|
| 1–5 | 16 | ||
| 6–10 | |||
| 11–14 | |||
| 15–16 | 10 | ||
| 17–20 |