#P5454. [THUPC2018] 城市地铁规划

[THUPC2018] 城市地铁规划

题目描述

经过选拔,Kiana成为了可乐城的市长,为了兑现选举承诺,她决定在可乐城的 nn 个重要地标之间修建地铁。

可乐城的交通状况并不复杂,在任意两个地标之间修建一条地铁轨道都是可行的,但是地铁轨道并不是越多越好,如果有太多地铁从一个地标处经过,该地标的拥堵程度将大幅增加。为此,Kiana决定给每个地标一个便利度来衡量拥堵程度,如果有 dd 条地铁轨道经过了某个地标,那么该地标的便利度为 f(d)mod59393f(d)\mod 59393,其中 f(x)=i=0kaixif(x)=\sum_{i=0}^{k}a_ix^i 是Kiana指定的一个 kk 次多项式。

因为修建地铁有一定的成本,所以Kiana希望新建的地铁轨道尽可能少,但任意两座地标之间都需要能通过地铁相互到达。Kiana想知道在给定的条件下,什么样的修建方案可以使得地标的便利度之和最大。由于她不会做,所以希望你来告诉她答案。

输入格式

输入第一行包含两个正整数 nnkk,分别表示可乐城的地标总数和Kiana指定的多项式次数,地标的编号依次为 11nn,数据保证 n3000n\leq 3000k10k\leq 10

输入第二行包含 k+1k+1 个非负整数 a0aka_0\sim a_k,即Kiana指定的多项式的系数,数据保证所有的 ai50a_i\leq 50

输出格式

输出由若干行组成,第一行包含两个用空格隔开的正整数 mmSS,分别表示你的方案中修建的地铁轨道数量与最终的便利度之和。

接下来 mm 行,每行包含两个用空格隔开的正整数 uuvv,表示在第 uu 和第 vv 个地标之间修建了一条地铁轨道。

本题将采用Special Judge,如果有多种方案使得地标的便利度之和最大,输出其中任意一种即可。

4 2
0 0 1
3 12
1 2
1 3
1 4
10 9
10 9 8 7 6 5 4 3 2 1
9 177454
4 5
4 6
3 4
3 7
2 3
2 8
1 2
1 9
1 10

提示

备注

本题因为一些原因只保留了后 5050 组数据。

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。