logo AlgoBeat OnlineJudge
登录 注册

#10160. [Sleeping Cup #11] G. Interstellar JavaScript Seminar

内存限制:512 MiB 时间限制:1000 ms 输入文件:seminar.in 输出文件:seminar.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

如无特殊说明,题目中出现的所有数字均为十进制数字; 进制数字会以序列的方式写出,如 表示十进制下的

请注意,你需要求解的是「取模前最小的和对 取模的结果」,而非「对 取模后最小的和」。

作为提示,由 可知 取模的结果为 ,因此你可以使用 而非 进行计算来避免不必要的溢出问题。

题目背景纯属虚构,不影射现实中的任何个人或团体。

>>> [1, 2, 4, 8, 16, 32, 64, 128].sort()
[1, 128, 16, 2, 32, 4, 64, 8]

一个很少有地球人知道的事实是,自 2015 年起,我们的吉祥物 Sleeping Kangaroo 每年 12 月 31 日都会乘飞机前往堪培拉,参加一场由外星人组织的星际 JavaScript 研讨会,与外星人们互相分享各自的 JavaScript 编程经验,并在随后举办的友谊赛中切磋技艺,11 年来受益匪浅。

时间来到 2026 年 1 月 6 日,这是 2025 - 2026 年度第 11 届星际 JavaScript 研讨会日程的第七天,主持人正在揭晓友谊赛的比赛成绩,而整个研讨会也将在第二天结束。

「下面揭晓各题目通过情况!问题 A,提交 4881 人,通过 4880 人……」

「啊?」Sleeping Kangaroo 大吃一惊,因为上次有人没能在友谊赛中通过问题 A 还是在 10 年前的 2015 - 2016 年度第 1 届星际 JavaScript 研讨会。

颁奖典礼结束后,Sleeping Kangaroo 找到了这位倒霉的研讨会会员,开始耐心地帮他复盘。

「我……我只是个 JavaScript 新手,很多知识点还不熟。对于场上的问题 A,我对着那个传进来的正整数数组直接调用了 sort 方法,然后……然后……」

正如你在题目背景开头看到的,JavaScript 对正整数数组的默认排序行为是对这些正整数按一般书写习惯(高位在前,省略前导 0)写成字符串后按字符串的字典序排升序,而不是按照这些正整数的实际大小排升序。

「让我来教教你吧,sort 方法在对数字排序时要用 sort((a, b) => a - b) 来按照数字大小排升序,而不能使用默认的比较方式。举个例子,对于问题 A 的样例……样例……」

咦,题目归档中的样例呢?

由于外星人有 根手指,他们使用的 JavaScript 也是基于 进制计数的,并且字符编码中有 种对应的数字字符,字典序从小到大分别是 。(在具体实现中,它们的编码分别为 ,每个数字字符占用 字节空间;当然了,这对解题不重要)

问题 A 的样例中包含一个长度为 的正整数序列,按数字从小到大分别为 ,且其中任意两项不相等。

然而,根据这位会员在赛场上的样例自测记录,他错误地调用了 sort 方法,将这些数字按一般书写习惯(高位在前,省略前导 )写成字符串后按字符串的字典序排升序,最后得到了序列 ,其中 是一个 的排列。

Sleeping Kangaroo 知道,现在要是跑去组委会获取样例的话,这位会员会等得不耐烦的。为了方便分析,你能帮 Sleeping Kangaroo 构造一个这样的序列,使得这 个正整数的和最小吗?

由于 进制数字难以输出,你只需要输出最小的和。

答案对 取模。

输入格式

第一行一个正整数

第二行一个 的排列

输出格式

一行一个非负整数表示答案。

答案对 取模。

样例

样例输入 #1

10
1 2 3 4 5 6 7 8 9 10

样例输出 #1

55

样例输入 #2

10
10 9 8 7 6 5 4 3 2 1

样例输出 #2

111111113

样例输入 #3

10
7 9 10 5 8 4 2 1 6 3

样例输出 #3

223147

数据范围与提示

样例 1 解释

一个可能的序列 是:

总和为

样例 2 解释

一个可能的序列 是:

总和为

样例 3 解释

一个可能的序列 是:

总和为