#P17694. Quark and Graph
Quark and Graph
题目描述
现有一张边权全为 的有标号简单无向连通图,其包含 个节点和 条边,已知该图上点 到所有点的最短路长,求这张图有多少种形态。
特别地,我们认为点 到点 的最短路为 。
两个图的形态不同当且仅当存在至少一条边 在一张图中出现且在另一张图中没出现。
由于 little_sun 太巨了,所以数据保证至少存在一张满足条件的图。
答案对 取模。
输入格式
第一行两个正整数 —— 表示图的节点数, 表示图的边数。
第二行 个非负整数 表示点 到其它点的最短路。
输出格式
输出一行一个整数表示你的答案。
输入输出样例 #1
输入 #1
4 3
0 1 1 2
输出 #1
2
输入输出样例 #2
输入 #2
5 5
0 1 1 2 2
输出 #2
12
输入输出样例 #3
输入 #3
8 12
0 2 2 2 2 1 1 1
输出 #3
128601
说明/提示
样例解释
对于第一个样例,有 和 两种形态。
对于第二个样例,我想到了一个绝妙的解释,可惜这里空白太小,写不下。
数据范围
本题采用捆绑测试。
- Subtask 1(10 pts),满足 ,,时限 1s;
- Subtask 2(20 pts),满足 ,,时限 1s;
- Subtask 3(20 pts),满足 ,,时限 1s;
- Subtask 4(50 pts),无特殊限制,时限 3s。
对于 的数据,满足 ,。设 ,还应满足 。
本题强制开启 O2 优化。