给定一个大小为 $K$ 的环 $R$。

\\n

环是一类包含两种运算（乘法 $\\\\otimes$ 和加法 $\\\\oplus$）的代数系统，满足

\\n

$\\\\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$ 中的元素），定义向量加法\\n$$\\n\\\\boldsymbol{u}+\\\\boldsymbol{v}=(u_1\\\\oplus v_1,u_2\\\\oplus v_2,\\\\dots,u_N\\\\oplus v_N)\\n$$\\n以及数量乘法\\n$$\\na\\\\cdot \\\\boldsymbol{u}=(a\\\\otimes u_1,a\\\\otimes u_2,\\\\dots,a\\\\otimes u_N)\\n$$\\n（这里 $a∈R$）。

\\n

对于一个向量集合 $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

称一个 $N$ 维向量集合 $S$ 是一个完全表示，当且仅当它能够表示所有 $N$ 维向量。

\\n

求所有 $N$ 维完全表示的大小的 $M$ 次方和对 $164511353$（一个质数）取模的结果。

\\n

输入格式

\\n

第一行输入三个数 $N,K,M$。

\\n

第二行输入一个数 $tp$。

\\n

我们认为 $R$ 中的每个元素唯一对应 $[0,K)$ 中的一个整数。特别地，保证加法单位元对应 $0$，乘法单位元对应 $1$。

\\n

如果 $tp=1$，则 $∀i,j∈R$，$i⊕j=(i+j)\\\\bmod K$，$i\\\\otimes j=(i\\\\times j)\\\\bmod K$。

\\n

如果 $tp=2$，接下来输入 $2K$ 行每行 $K$ 个数。

\\n

对于前 $K$ 行，第 $i+1$ 行的第 $j+1$ 个元素表示 $i⊕j$。

\\n

对于后 $K$ 行，第 $i+1$ 行的第 $j+1$ 个元素表示 $i⊗j$。

\\n

输出格式

\\n

输出一行一个数，表示答案对 $164511353$ 取模的结果。

\\n

样例 1

\\n

输入

\\n

统计

递交统计

[集训队互测 2022day7]完全表示

信息

状态

开发

支持

关于

登录