作者ledia (tricky situation)
看板ACMCLUB
标题Re: 1018 练习赛
时间Sun Oct 19 15:09:33 2003
※ 引述《smartboy (小光光)》之铭言：
: H 线性代数问题, 解法可能跟同余系 matrix/inverse/determine 有关
: 题目有怪条件: sly number in set {0,1,2} 不知道怎麽用
提供一个想法, 不确定这个方向够不够好
N=5 for example:
C[0] = A[0]B[0] + A[1]B[4] + A[2]B[3] + A[3]B[2] + A[4]B[1]
C[1] = A[0]B[1] + A[1]B[0] + A[2]B[4] + A[3]B[3] + A[4]B[2]
C[2] = A[0]B[2] + A[1]B[1] + A[2]B[0] + A[3]B[4] + A[4]B[3]
C[3] = A[0]B[3] + A[1]B[2] + A[2]B[1] + A[3]B[0] + A[4]B[4]
C[4] = A[0]B[4] + A[1]B[3] + A[2]B[2] + A[3]B[1] + A[4]B[0]
C[0] A[1] A[2] A[3] A[4] A[0] | B[4]
C[1] A[2] A[3] A[4] A[0] A[1] | B[3]
C[2] = A[3] A[4] A[0] A[1] A[2] | B[2] ( matrix representation )
C[3] A[4] A[0] A[1] A[2] A[3] | B[1]
C[4] A[0] A[1] A[2] A[3] A[4] | B[0]
其中 A 已知, C[0] = 1 (mod Q), C[i] = 0 (mod Q) for 0<i<N
考虑把四个式子加在一起会得到
4 4 4
sigma C[i] = ( sigma A[i] ) * ( sigma B[i] ) (mod Q)
i=0 i=0 i=0
4
但是 sigma C[i] = 1 (mod Q), 所以显然
i=0
4
gcd (sigma A[i], Q) = 1, 否则会无解! ( a simple test here )
i=0
4 4
又从上式得知, sigma A[i] 可以求 inv, 所以 sigma B[i] = A^(-1) (mod Q)
i=0 i=0
我不确定拿这一个东西回去和原本的式子线性组合会不会有什麽好性质
不过各个 digit 只能有 {0,1,2} 应该能有不错的应用, 大家继续想一想吧~
( 或许能把 {0,1,2} 换成 {-1,0,1} 也会有好应用? ^^" )
--
有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。
存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你
，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也
是比较不容易被击倒的人。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.37
※ 编辑: ledia 来自: 140.112.30.37 (10/19 15:10)
※ 编辑: ledia 来自: 140.112.30.37 (10/19 15:10)
※ 编辑: ledia 来自: 140.112.30.37 (10/19 15:15)
※ 编辑: ledia 来自: 140.112.30.37 (10/19 15:52)
※ 编辑: ledia 来自: 140.112.30.37 (10/20 09:39)