×

计蒜客

  1. 题库
  2. Tree
  3. 问答
  • 13.94%
  • 9000ms
  • 262144K

There is a tree with $n$ nodes, at which attach a binary $64*64$ matrix $M_i (1 \le i \le n)$. There are $q$ queries for matrix multiplication on the path from node $a$ to node $b$ modulo $2$. To avoid massive input dataset, $M_i(1\le i \le n)$ is attained by the following algorithm:

Input a random $seed$ (unsigned long long)

for(int i = 1; i <= n; ++i) {
    for(int p = 1; p <= 64; ++p) {
        seed ^= seed * seed + 15;
        for(int q = 1; q <= 64; ++q) {
            M[i][p][q] = (seed >> (q - 1)) & 1;
        }
    }
}

To avoid massive output, you should output$$\displaystyle (\displaystyle \sum_{i=1}^{64} \sum_{j=1}^{64} M_{ij}*19^i*26^j) \mod 19260817$$

Input Format

There are multi datasets. $(\sum n \le 3000, \sum q \le 30000)$.

For each dataset:

In the first $n-1$ lines, there are to integers $u,v$, indicates there is an edge connects node $u$ and node $v$.$(1\le u,v \le n)$.

In the next line there is an integer $seed(0 \le seed < 2^{64})$.

In the next $q$ lines, there is to integers $a,b$, indicates a query on path from node $a$ to node $b$.$(1 \le a,b \le n)$.

Output Format

For each query, output an integer in one line without any additional space.

样例输入

6 5
4 1
3 4
6 4
5 3
2 3
19260817
4 5
5 6
4 4
2 1
2 2

样例输出

4855239
2667906
277543
14478924
1173682

题目来源

2017 ACM-ICPC 亚洲区(西安赛区)网络赛

想挑战这道题吗

  • main.c