#P10331. 攻城带獅

    ID: 9449 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-整除 Zeta 变换莫比乌斯反演乘法分配律线性筛深度优先搜索欧几里得算法

攻城带獅

题目描述

有 nn 座城市,编号为 1,…,n1,\ldots,n,第 ii 座城市有一个正整数收益 aia_i。每回合选择一个非空城市集合并攻打,回合收益为所选城市收益的最大公约数。回合结束后城市恢复,整个过程中每个集合最多选择一次。

进行 kk 个回合,使回合收益之和最大。收益相同的方案按以下优先级比较。将两个集合分别按城市编号升序列出,比较第一个不同的位置,该位置编号较小的方案优先。如果一个序列是另一个序列的前缀,较短者优先。满足最大总收益的前提下,优先选取优先级更高的同收益方案。

一个攻击方案的哈希值为其所有城市编号的乘积。求选中的 kk 个方案哈希值之和,对 2322^{32} 取模。

输入格式

第一行两个整数 n,kn,k。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

若不存在 kk 个不同的非空集合,输出 -1。否则输出一行一个整数,表示哈希值之和对 2322^{32} 取模的结果。

样例 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。

数据范围

测试点 nn 上界 kk 上界 aia_i 上界
1–5 16 2×1042\times10^4 3×1053\times10^5
6–10 10310^3 2×1032\times10^3 5×1035\times10^3
11–14 10510^5 5×1055\times10^5 10510^5
15–16 10
17–20 2×1052\times10^5 3×1063\times10^6 10710^7

原 PDF 题面