#PQJ759x4908. QOJ 759_4908
QOJ 759_4908
标题: 完全表示 - Problem - QOJ.ac
#4908. 完全表示
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