Skip to content

11393: 【原1393】进击の哔酱

题目

题目描述

author: 徐世超 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1393

Description

WARNING:一定要将题目读完了再思考!!!

哔酱获得了一个奇妙的道具,这个道具能够让哔酱获得任何异性的好感,但这个道具有冷却时间,每隔k天可以使用一次, 而且必须当天使用(某次使用后的第k天当天可以再次使用)。哔酱希望捕获更多人的芳心,所以每一次的使用道具的机会他都不会放弃。 酱星人的地图是一个有m个城市q条通道的无向图,每条通道连接两条城市, 哔酱每一天可以从一个城市到达另一个相邻的城市,或者他可以选择停留在这个城市休息一天。 他一开始在起点S,此时道具也刚好开始冷却。 哔酱有n个心仪的异性,并且他通过首长获取了这些异性所在城市的坐标(两两不同), 已知第i次对第j个异性使用道具可以得到a[i,j]点好感度,

哔酱发现从一个城市到另一个城市有很多条不同的路径、使用道具的顺序不同导致获得的好感度也不同……他想知道最终好感度最高是多少, 以及在保证最终好感度最高的情况下,他从起点到最后一个被使用道具的异性所在的城市有多少种不同的路径,他发现答案可能会非常大, 于是他只想要知道答案对p取模的值。不同路径是指依次走过的道路有所不同(停留可以看作是走向自己的道路),而不是依次经过的城市有所不同。

Input Format

第一行有六个空格隔开的正整数m,q,n,s,k,p,分别表示图中城市数和道路数,哔酱心仪的异性人数,起点的编号,道具冷却时间以及模数。

第二行有n个空格隔开的正整数,第i个正整数表示编号为i的哔酱心仪的一个异性所在城市的编号。

接下来n行,每行有n个空格隔开的整数,第i行j列的整数a{i,j}表示第i次遇见第j个异性可以增加的a{i,j}点好感度。 注意每个异性仅需也仅能遇见一次,因为哔酱喜新厌旧。

接下来q行,第i行两个空格隔开的正整数ui,vi,表示编号为ui和编号为vi的城市之间有一条编号为i的道路, ui != vj。

Output Format

两个空格隔开的整数,表示最优的最终获得的好感度和相应的路径方案数模p的值。

Sample Input

7 12 6 1 1 233
2 3 4 5 6 7
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 3
3 4
4 5
5 6
6 7
7 2

Sample Output

6 12

数据范围与约定

对于30%的数据:k=1

对于60%的数据:a{i,j}=1

对于100%的数据: 1<=m<=50 ,1<=q<=1000, 1<=n<=12, -1<=a{i,j}<=1, 1<=k<2^31, 1<=p<2^31 。

样例解释

异性所在的点2~6围成一个环,点1均可到达2~6,哔酱可以从1任选一条路,然后选择按照编号单调递增或递减的顺序遍历异性所在的城市,共6*2=12种方法。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!