#P12865. 抽象代数

    ID: 12051 传统题 6000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3100组合数学多项式FFT状压DP数学2025“钉耙编程”中国大学生算法设计暑期联赛(9)

抽象代数

抽象代数

Problem Description

在 U={ 1,2,⋯ ,n }U= \set{ 1, 2, \cdots, n } 上定义有结合律的二元运算 ⊕\oplus 满足 ∀a,b∈U,a⊕b∈{a,b}\forall a,b\in U, a\oplus b\in \{a,b\}。 对于一个运算 ⊕\oplus,称数 xx 是交换子当且仅当 ∀y∈U,x⊕y=y⊕x\forall y\in U, x\oplus y=y\oplus x。 已知 mm 个形如 a⊕b=ca\oplus b=c 的等式(1≤a,b≤K≤171\le a,b\le K\le 17,c∈{a,b}c\in \{a,b\}),对于所有可能的 ⊕\oplus 求 2交换子个数2^{\text{交换子个数}} 和。

Input

首先输入三个自然数 n,m,Kn,m,K(2≤n≤1052\le n\le 10^5,0≤m≤K20\le m \le K^2,1≤K≤171\le K\le 17),分别表示元素个数、已知等式个数和已知等式的数字范围。 之后有 mm 行,每行有三个正整数 a,b,ca,b,c(1≤a,b≤K1\le a,b\le K,c∈{a,b}c\in \{a,b\}),表示一个等式 a⊕b=ca\oplus b=c。

Output

输出一行一个自然数,表示答案除以 998244353998244353 的余数。

Sample Input

3 3 3
1 2 1
2 3 2
2 1 2

Sample Output

3

Hint

我们把已知信息列成一张表,未知部分用字母表示:

aa \ a⊕ba\oplus b \ bb 11 22 33
11 1\boxed{1} 11 1\color{green}{1}
22 2\boxed{2} 22
33 pp qq 3\boxed{3}
其中,方框内数字由“a\oplus b\in \{a,b\} ​”可以自动得到;黑色数字是输入的条件。
现在还有两个空 p,qp,q 没填,对两个空进行枚举:
  • p=1,q=2p=1,q=2:符合题意,此时交换子有 33。
  • p=3,q=2p=3,q=2:(3⊕1)⊕2≠3⊕(1⊕2) (3\oplus 1) \oplus 2 \ne 3 \oplus (1\oplus 2) 。
  • p=1,q=3p=1,q=3:(3⊕2)⊕1≠3⊕(2⊕1) (3\oplus 2) \oplus 1 \ne 3 \oplus (2\oplus 1) 。
  • p=3,q=3p=3,q=3:符合题意,此时没有交换子。 因此你输出 21+20=32^1+2^0=3。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(9)