#PQJ759x4908. QOJ 759_4908

    ID: 3036 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2021 集训队互测枚举组合数学

QOJ 759_4908

标题: 完全表示 - Problem - QOJ.ac

#4908. 完全表示

Statistics

The problem was used in the following contests:

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

环是一类包含两种运算(乘法 ⊗ 和加法 ⊕)的代数系统,满足

  • ∀a,b,c∈R,(a⊕b)⊕c=a⊕(b⊕c)(加法结合律)
  • ∀a,b∈R,a⊕b=b⊕a(加法交换律)
  • ∀a∈R,a⊕0=a(加法单位元)
  • ∀a∈R,∃(−a)∈R,a⊕(−a)=0(加法逆元)
  • ∀a,b,c∈R,(a⊗b)⊗c=a⊗(b⊗c)(乘法结合律)
  • ∀a∈R,1⊗a=a⊗1=a(乘法单位元)
  • ∀a,b,c∈R,a⊗(b⊕c)=(a⊗b)⊕(a⊗c),(b⊕c)⊗a=(b⊗a)⊕(c⊗a)(分配律)

考虑所有 N 维向量 u=(u1,u2,…,uN)(这里的每 u 一维都是 R 中的元素),定义向量加法

u+v=(u1⊕v1,u2⊕v2,…,uN⊕vN)

以及数量乘法

a⋅u=(a⊗u1,a⊗u2,…,a⊗uN)

(这里 a∈R)。

对于一个向量集合 S={s1,s2,…,sn},我们称其能够表示 u 当且仅当。∃a1,a2,…,an∈R,∑i=1naisi=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)modK,i⊗j=(i×j)modK。

如果 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×23+4×33+1×43=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 KN≤20 10 2 ≤20 是质数 =0 15 3 ≤1000 5 4 5 5 ≤100 15 6 5 7 ≤100 ≤100 15 8 15 9 ≤20 2 15

时间限制:1s

空间限制:1GB