102947: [Atcoder]ABC294 Ex - K-Coloring
Description
Score : $600$ points
Problem Statement
You are given a simple undirected graph with $N$ vertices numbered $1$ to $N$ and $M$ edges numbered $1$ to $M$. Edge $i$ connects vertex $u_i$ and vertex $v_i$.
Find the number, modulo $998244353$, of ways to write an integer between $1$ and $K$, inclusive, on each vertex of this graph to satisfy the following condition:
- two vertices connected by an edge always have different numbers written on them.
Constraints
- $1 \leq N \leq 30$
- $0 \leq M \leq \min \left(30, \frac{N(N-1)}{2} \right)$
- $1 \leq K \leq 10^9$
- $1 \leq u_i \lt v_i \leq N$
- The given graph is simple.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
Output
Print the number, modulo $998244353$, of ways to write integers between $1$ and $K$, inclusive, on the vertices to satisfy the condition.
Sample Input 1
4 3 2 1 2 2 4 2 3
Sample Output 1
2
Here are the two ways to satisfy the condition.
- Write $1$ on vertices $1, 3, 4$, and write $2$ on vertex $2$.
- Write $1$ on vertex $2$, and write $2$ on vertex $1, 3, 4$.
Sample Input 2
4 0 10
Sample Output 2
10000
All $10^4$ ways satisfy the condition.
Sample Input 3
5 10 5 3 5 1 3 1 2 1 4 3 4 2 5 4 5 1 5 2 3 2 4
Sample Output 3
120
Sample Input 4
5 6 294 1 2 2 4 1 3 2 3 4 5 3 5
Sample Output 4
838338733
Sample Input 5
7 12 1000000000 4 5 2 7 3 4 6 7 3 5 5 6 5 7 1 3 4 7 1 5 2 3 3 6
Sample Output 5
418104233
Input
题意翻译
zjh 有一个有 $n$ 个顶点、$m$ 条边的简单无向图。 求出有多少种填数方案使得,在这个图的每个顶点中填入一个 $1$ 到 $k$ 之间的整数之后每条边所连的两个点上的数都不同。你只需要输出方案数对 $998244353$ 取模的值。 Translated by @[Zealous_YH](https://www.luogu.com.cn/user/399150)Output
问题描述
你有一个简单的无向图,有N个编号为1到N的顶点和M个编号为1到M的边。第i条边连接顶点u_i和顶点v_i。
找到满足以下条件的在每个顶点上写一个1到K(包括1和K)之间的整数的方法的数量,取模数为998244353:
- 由边连接的两个顶点总是写有不同的数字。
约束条件
- 1≤N≤30
- 0≤M≤min(30,N(N-1)/2)
- 1≤K≤10^9
- 1≤u_i<v_i≤N
- 给定的图是简单的。
输入
输入从标准输入按以下格式给出:
$N$ $M$ $K$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
输出
打印出满足条件的在顶点上写整数的方法的数量,取模数为998244353。
样例输入1
4 3 2 1 2 2 4 2 3
样例输出1
2
以下是满足条件的两种方法。
- 在顶点1、3、4上写1,在顶点2上写2。
- 在顶点2上写1,在顶点1、3、4上写2。
样例输入2
4 0 10
样例输出2
10000
所有$10^4$种方法都满足条件。
样例输入3
5 10 5 3 5 1 3 1 2 1 4 3 4 2 5 4 5 1 5 2 3 2 4
样例输出3
120
样例输入4
5 6 294 1 2 2 4 1 3 2 3 4 5 3 5
样例输出4
838338733
样例输入5
7 12 1000000000 4 5 2 7 3 4 6 7 3 5 5 6 5 7 1 3 4 7 1 5 2 3 3 6
样例输出5
418104233