Boboniu Walks on Graph
Contest: Codeforces Round 664 (Div. 1)
Difficulty rating: 2300
Tags: brute force, dfs and similar, graphs, hashing

Boboniu has a directed graph with $$$n$$$ vertices and $$$m$$$ edges.

The out-degree of each vertex is at most $$$k$$$.

Each edge has an integer weight between $$$1$$$ and $$$m$$$. No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple $$$(c_1,c_2,\ldots,c_k)$$$. If he now stands on a vertex $$$u$$$ with out-degree $$$i$$$, then he will go to the next vertex by the edge with the $$$c_i$$$-th $$$(1\le c_i\le i)$$$ smallest weight among all edges outgoing from $$$u$$$.

Now Boboniu asks you to calculate the number of tuples $$$(c_1,c_2,\ldots,c_k)$$$ such that

- $$$1\le c_i\le i$$$ for all $$$i$$$ ($$$1\le i\le k$$$).
- Starting from any vertex $$$u$$$, it is possible to go back to $$$u$$$ in finite time by walking on the graph under the described rules.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$2\le m\le \min(2\cdot 10^5,n(n-1) )$$$, $$$1\le k\le 9$$$).

Each of the next $$$m$$$ lines contains three integers $$$u$$$, $$$v$$$ and $$$w$$$ $$$(1\le u,v\le n,u\ne v,1\le w\le m)$$$, denoting an edge from $$$u$$$ to $$$v$$$ with weight $$$w$$$. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most $$$k$$$ and no two edges have equal weight.

Output format:
Print one integer: the number of tuples.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first example, there are two tuples: $$$(1,1,3)$$$ and $$$(1,2,3)$$$. The blue edges in the picture denote the $$$c_i$$$-th smallest edges for each vertex, which Boboniu chooses to go through.

For the third example, there's only one tuple: $$$(1,2,2,2)$$$.

The out-degree of vertex $$$u$$$ means the number of edges outgoing from $$$u$$$.

Example input:
4 6 3
4 2 1
1 2 2
2 4 3
4 1 4
4 3 5
3 1 6

Example output:
2

Example input:
5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5

Example output:
1

Editorial:
Let $$$\deg u$$$ denote the out degree of $$$u$$$. Let $$$nex_{u,i}$$$ denote the vertex, which the edge with the $$$i$$$-the smallest weight among all edges start from $$$u$$$ ends at.
For a fixed tuple $$$(t_1,t_2,\ldots,t_k)$$$, if $$$\{ nex_{i,t_{\deg i}} | 1\le i\le n \}=\{1,2,\ldots,n\}$$$ (i. e. each vertex appears exactly once), then it is a correct tuple.
Let $$$S_{i,j}$$$ denote if $$$c_i=j$$$, the set for vertex with out degree $$$i$$$, which is $$$\{ nex_{u,j} | \deg u=i \}$$$. Thus the condition above can be changed to: $$$S_{1,t_1} \cup S_{2,t_2} \cup \ldots \cup S_{k,t_k}=\{1,2,\ldots,n\} $$$.
Let's enumerate all $$$k!$$$ situations and use hash to check if it's correct.
The hash function is diverse. For example, for a integer set $$$T$$$, we can use $$$h(T)=\sum_{x\in T}val_x\bmod p$$$ or $$$h(T)=\prod_{x\in T}val_x\bmod p$$$. Just make sure it has associative property. Here $$$val_x$$$ may be a random number. Let alone using multiple hash.
The total time complexity is $$$O(n+m+k!)$$$.