给定一个大小为 $K$ 的环 $R$。
环是一类包含两种运算(乘法 $\otimes$ 和加法 $\oplus$)的代数系统,满足
- $\forall a,b,c\in R,(a\oplus b)\oplus c=a\oplus (b\oplus c)$(加法结合律)
- $\forall a,b\in R,a\oplus b=b\oplus a$(加法交换律)
- $\forall a\in R,a\oplus 0=a$(加法单位元)
- $\forall a\in R,\exists (-a)\in R,a\oplus (-a)=0$(加法逆元)
- $\forall a,b,c\in R,(a\otimes b)\otimes c=a\otimes(b\otimes c)$(乘法结合律)
- $\forall a\in R,1\otimes a=a\otimes 1=a$(乘法单位元)
- $\forall a,b,c\in R,a\otimes(b\oplus c)=(a\otimes b)\oplus (a\otimes c),(b\oplus c)\otimes a=(b\otimes a)\oplus (c\otimes a)$(分配律)
考虑所有 $N$ 维向量 $\boldsymbol u=(u_1,u_2,…,u_N)$(这里的每 $\boldsymbol u$ 一维都是 $R$ 中的元素),定义向量加法 $$ \boldsymbol{u}+\boldsymbol{v}=(u_1\oplus v_1,u_2\oplus v_2,\dots,u_N\oplus v_N) $$ 以及数量乘法 $$ a\cdot \boldsymbol{u}=(a\otimes u_1,a\otimes u_2,\dots,a\otimes u_N) $$ (这里 $a∈R$)。
对于一个向量集合 $S=\{\boldsymbol{s_1},\boldsymbol{s_2},\dots,\boldsymbol{s_n}\}$,我们称其能够表示 $\boldsymbol u$ 当且仅当。$\exists a_1,a_2,\dots,a_n\in R,\sum_{i=1}^{n}a_i\boldsymbol{s_i}=\boldsymbol{u}$
称一个 $N$ 维向量集合 $S$ 是一个完全表示,当且仅当它能够表示所有 $N$ 维向量。
求所有 $N$ 维完全表示的大小的 $M$ 次方和对 $164511353$(一个质数)取模的结果。
输入格式
第一行输入三个数 $N,K,M$。
第二行输入一个数 $tp$。
我们认为 $R$ 中的每个元素唯一对应 $[0,K)$ 中的一个整数。特别地,保证加法单位元对应 $0$,乘法单位元对应 $1$。
如果 $tp=1$,则 $∀i,j∈R$,$i⊕j=(i+j)\bmod K$,$i\otimes j=(i\times j)\bmod K$。
如果 $tp=2$,接下来输入 $2K$ 行每行 $K$ 个数。
对于前 $K$ 行,第 $i+1$ 行的第 $j+1$ 个元素表示 $i⊕j$。
对于后 $K$ 行,第 $i+1$ 行的第 $j+1$ 个元素表示 $i⊗j$。
输出格式
输出一行一个数,表示答案对 $164511353$ 取模的结果。
样例 1
输入
2 2 3
2
0 1
1 0
0 0
0 1
输出
196
解释
全体完全表示为:$\{(0,0)(0,1)(1,0)\}$,$\{(0,0)(0,1)(1,1)\}$,$\{(0,0)(1,0)(1,1)\}$,$\{(0,0)(0,1)(1,0)(1,1)\}$,$\{(0,1)(1,0)\}$,$\{(0,1)(1,1)\}$,$\{(1,0)(1,1)\}$,$\{(0,1)(1,0)(1,1)\}$,答案为 $3\times 2^3+4\times 3^3+1\times 4^3=196$
样例 2
输入
2 3 3
2
0 1 2
1 2 0
2 0 1
0 0 0
0 1 2
0 2 1
输出
61995
解释
该样例输入等价于
2 3 3
1
样例 3
输入
2 4 1
2
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2
输出
524132
限制与约定
对于所有数据,$1≤N≤100000,2≤K≤100000,0≤M≤1000,∀i,j∈R,i⊕j,i⊗j∈[0,K)$,保证输入是一个合法的环。
子任务编号 | $N$ | $K$ | $M$ | $tp$ | 特殊性质 | 分值 |
---|---|---|---|---|---|---|
$1$ | $ $ | $ $ | $ $ | $1$ | $K^N\le 20$ | $10$ |
$2$ | $\le 20$ | 是质数 | $=0$ | $ $ | $15$ | |
$3$ | $\le 1000$ | $5$ | ||||
$4$ | $ $ | $5 $ | ||||
$5$ | $\le 100$ | $15$ | ||||
$6$ | $ $ | $5$ | ||||
$7$ | $\le 100$ | $\le 100$ | $15$ | |||
$8$ | $ $ | $ $ | $15 $ | |||
$9$ | $\le 20$ | $2$ | $15$ |
时间限制:1s
空间限制:1GB