QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

# 7794. 水果茶

统计

水果茶是一种广受好评的饮料。制作水果茶需要将两种原料混合。设两种原料的权值分别为 $ x,y $,则制成的水果茶的“美味度”为 $ x\times y $。SG 城的市场可以看做一张仙人掌图,每个点代表一个摊位,每个摊位上有一种原料。苏师傅发现距离为 $ k $ 的两个摊位的原料最适合制作水果茶。他想让你帮他求出制作所有可能的水果茶的“美味度”之和。答案对 $ 1315105 $ 取模。

简要题意:求仙人掌图上所有距离为 $ k $ 的点对的权值积的和。

两个摊位的距离指他们在图上的最短路径经过的边数。

输入格式

第一行三个整数 $ n,m,k $,分别表示仙人掌的点数、边数与点对间的距离。

接下来 $ m $ 行每行两个整数 $ u,v $ 表示仙人掌的一条边。

接下来一行 $ 1 $ 个整数 $ seed $,选手根据 $ seed $ 运行如下代码得到每个点的权值 $ a_i $。

mt19937_64 rnd(seed);
int MAXM=1e9;
for(int i=1;i<=n;i++)a[i]=rnd()%MAXM+1;

输出格式

输出一行一个整数表示答案。

样例

样例输入
12 14 4
1 2
2 3
1 4
4 5
3 5
5 6
6 7
5 7
7 8
8 9
9 10
7 10
3 11
11 12
27455
样例输出
578532

数据规模与约定

对于所有数据,$ 1\le n,m,k\le 5\times 10^6 $,$ \forall i,1\le a_i\le 10^9 $,$ seed\le 10^9 $。

子任务 1(10 分):$ n,m,k\le 3500 $。

子任务 2(10 分):$ n,m,k\le 10^5 $,$ m=n-1 $。

子任务 3(10 分):$ n,m,k\le 10^5 $,$ m=n $。

子任务 4(10 分):$ n,m,k\le 10^5 $,$ m\le n+20 $。

子任务 5(20 分):$ n,m,k\le 10^5 $,保证仙人掌的环长不超过 $ 20 $。

子任务 6(20 分):$ n,m,k\le 10^5 $。

子任务 7(20 分):无特殊性质。

特别提醒:由于本题输入量极大,建议使用下发快读。

char ch,B0[1<<15],*S=B0,*T=B0;
#define getc() (S==T&&(T=(S=B0)+fread(B0,1,1<<15,stdin),S==T)?0:*S++)
inline int read(){
    int aa;
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';
    return aa;
}