QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 4908. 完全表示

统计

给定一个大小为 $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