#1802. 水果茶

    ID: 1802 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1425来源:qoj.ac数据:公开样例最短路径差分

水果茶

水果茶

题目描述

标题: 水果茶 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

输入格式

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

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

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

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≤n,m,k≤5×106,∀i,1≤ai≤109,seed≤109。

子任务 1(10 分):n,m,k≤3500。

子任务 2(10 分):n,m,k≤105,m=n−1。

子任务 3(10 分):n,m,k≤105,m=n。

子任务 4(10 分):n,m,k≤105,m≤n+20。

子任务 5(20 分):n,m,k≤105,保证仙人掌的环长不超过 20。

子任务 6(20 分):n,m,k≤105。

子任务 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;
}

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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