Travel plan

Bob lives on a magical land. There are $n$ cities and $m$ roads on the land. The length of the $i$-th road is $w_i$, and the length is an integer between $1$ and $L$. Each road connects two cities. The land can be viewed as a graph of $n$ points and $m$ edges.

This land is magical because Bob was surprised to find that there are no simple circuits with an even total length in this land!

Bob likes to travel. If Bob takes a simple path from $x$ to $y$ $(x < y)$, the happiness value is the greatest common factor (gcd) of the lengths of all roads on the path.

simple path:A path is called a simple path if the vertices on the path do not repeat each other.

simple circuit:A circuit in which the vertices are not repeated except for the first and last vertices is called a simple circuit

Bob wants to count all possible travel paths.

Define $F(k)$ as the total number of travel paths with happiness value k, modulo 998244353.

Please find $F(1) \bigoplus F(2) \bigoplus F(3) \bigoplus ... \bigoplus F(L)$,where $\bigoplus$ represents XOR.

The first line contains an integer $T(T \le 500)$ —the number of test cases.

The first line of each test case contains 3 integers $n,m,L(1 \le n,L \le 100000,1 \le m \le 200000)$ —number of cities, number of roads, length range of roads.

The next $m$ lines , each line contains 3 integers $u_i,v_i,w_i(1 \le u_i,v_i \le n,1 \le w_i \le L)$ —.represents a road of length $w_i$ connecting $u_i, v_i$.

It is guaranteed that there are no double edges and self-loops.

$1 \le \sum n,\sum L \le 500000,1 \le \sum m \le 1000000$

For each test case, output a line containing an integer representing the answer.

3
3 3 6
1 2 6
2 3 4
3 1 5
5 4 10
1 2 10
1 3 1
2 4 7
1 5 4
7 8 7
1 2 4
2 3 1
2 4 2
2 5 2
5 6 4
2 7 4
7 1 1
6 2 1

2
6
47

2022“杭电杯”中国大学生算法设计超级联赛（1）

Close | Top

Administration