Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。このグラフの頂点には 1 から N の番号が付けられており、辺には 1 から M の番号が付けられています。辺 i は頂点 U_i と頂点 V_i の間を結んでいます。
整数 K, S, T, X が与えられます。以下の条件を満たす数列 A = (A_0, A_1, \dots, A_K) は何通りありますか?
- A_i は 1 以上 N 以下の整数
- A_0 = S
- A_K = T
- 頂点 A_i と頂点 A_{i + 1} の間を直接結ぶ辺が存在する
- 数列 A の中に整数 X\ (X≠S,X≠T) は偶数回出現する ( 0 回でも良い)
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割ったあまりを求めてください。
制約
- 入力は全て整数
- 2≤N≤2000
- 1≤M≤2000
- 1≤K≤2000
- 1≤S,T,X≤N
- X≠S
- X≠T
- 1≤U_i<V_i≤N
- i≠j ならば (U_i, V_i)≠(U_j, V_j)
入力
入力は以下の形式で標準入力から与えられる。
N M K S T X U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
答えを 998244353 で割ったあまりを出力せよ。
入力例 1
4 4 4 1 3 2 1 2 2 3 3 4 1 4
出力例 1
4
- (1, 2, 1, 2, 3)
- (1, 2, 3, 2, 3)
- (1, 4, 1, 4, 3)
- (1, 4, 3, 4, 3)
の 4 個が条件を満たします。(1, 2, 3, 4, 3) や (1, 4, 1, 2, 3) は 2 が奇数回出現するため、条件を満たしません。
入力例 2
6 5 10 1 2 3 2 3 2 4 4 6 3 6 1 5
出力例 2
0
グラフは連結であるとは限りません。
入力例 3
10 15 20 4 4 6 2 6 2 7 5 7 4 5 2 4 3 7 1 7 1 4 2 9 5 10 1 3 7 8 7 9 1 6 1 2
出力例 3
952504739
998244353 で割ったあまりを求めてください。
Score : 500 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges. The vertices are numbered from 1 through N, and the edges are numbered from 1 through M. Edge i connects Vertex U_i and Vertex V_i.
You are given integers K, S, T, and X. How many sequences A = (A_0, A_1, \dots, A_K) are there satisfying the following conditions?
- A_i is an integer between 1 and N (inclusive).
- A_0 = S
- A_K = T
- There is an edge that directly connects Vertex A_i and Vertex A_{i+1}.
- Integer X\ (X≠S,X≠T) appears even number of times (possibly zero) in sequence A.
Since the answer can be very large, find the answer modulo 998244353.
Constraints
- All values in input are integers.
- 2≤N≤2000
- 1≤M≤2000
- 1≤K≤2000
- 1≤S,T,X≤N
- X≠S
- X≠T
- 1≤U_i<V_i≤N
- If i ≠ j, then (U_i, V_i) ≠ (U_j, V_j).
Input
Input is given from Standard Input in the following format:
N M K S T X U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Print the answer modulo 998244353.
Sample Input 1
4 4 4 1 3 2 1 2 2 3 3 4 1 4
Sample Output 1
4
The following 4 sequences satisfy the conditions:
- (1, 2, 1, 2, 3)
- (1, 2, 3, 2, 3)
- (1, 4, 1, 4, 3)
- (1, 4, 3, 4, 3)
On the other hand, (1, 2, 3, 4, 3) and (1, 4, 1, 2, 3) do not, since there are odd number of occurrences of 2.
Sample Input 2
6 5 10 1 2 3 2 3 2 4 4 6 3 6 1 5
Sample Output 2
0
The graph is not necessarily connected.
Sample Input 3
10 15 20 4 4 6 2 6 2 7 5 7 4 5 2 4 3 7 1 7 1 4 2 9 5 10 1 3 7 8 7 9 1 6 1 2
Sample Output 3
952504739
Find the answer modulo 998244353.