QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#553642 | #8095. Lati@s | ohwphil | TL | 1566ms | 48740kb | Python3 | 8.4kb | 2024-09-08 17:03:19 | 2024-09-08 17:03:19 |
Judging History
answer
# I owe all credit to hos-lyric for this code.
# This is a Python implementation of the Nimber multiplication algorithm.
# ref: https://github.com/hos-lyric/libra/blob/master/algebra/nimber.h
# 10279 in decimal. G16 ** 3 = [1 << 15].
import sys
input=sys.stdin.readline
PRIMITIVE_ROOT = 0b10100000100111
G16 = PRIMITIVE_ROOT
group_size = 1 << 16
group_mask = group_size - 1
GF216_MASK = group_mask
GF232_MASK = (1 << 32) - 1
GF264_MASK = (1 << 64) - 1
exp = [0] * (group_size * 2)
log = [0] * group_size
square_table = [[0]*group_size, [0]*group_size, [0]*group_size, [0]*group_size]
sqrt_table = [[0]*group_size, [0]*group_size, [0]*group_size, [0]*group_size]
quad_inv_table = [[0]*group_size, [0]*group_size, [0]*group_size, [0]*group_size]
def calc_exp(x):
if x<0:
return 0
return exp[x]
# all multiplication functions are based on a mathematical fact listed here:
# https://math.stackexchange.com/questions/909304/algorithm-to-multiply-
# We denote + for nimber addition(xor) and * for nimber multiplication.
# Brackets([]) denote that the operation inside is done in normal integer arithmetic.
# F denotes a Fermat 2-power, i.e. F = 2 ** (2 ** n), where n is a non-negative integer.
# If a = a0 + a1 * F and b = b0 + b1 * F, then a * b = a0 * b0 + (a0 * b1 + a1 * b0) * F + a1 * b1 * F ** 2.
# But there is a fact that F ** 2 = F + [F / 2], so we can simplify the above expression to:
# a * b = a0 * b0 + (a0 * b1 + a1 * b0 + a1 * b1) * F + a1 * b1 * [F / 2].
# But, we can reduce the number of multiplications by using the following fact:
# a0 * b1 + a1 * b0 + a1 * b1 = (a0 + a1) * (b0 + b1) + a0 * b0.
def mul_slow(prec, a, b):
if a == 0 or b == 0:
return 0
if prec == 1:
return a & b
l = prec >> 1
a0 = a & ((1 << l) - 1)
a1 = a >> l
b0 = b & ((1 << l) - 1)
b1 = b >> l
a0b0 = mul_slow(l, a0, b0)
return (a0b0 ^ mul_slow(l, 1 << (l - 1), mul_slow(l, a1, b1))) | ((a0b0 ^ mul_slow(l, a0 ^ a1, b0 ^ b1)) << l)
def mul_by_231(a):
if a == 0:
return 0
a0 = a & GF216_MASK
a1 = a >> 16
a01 = a0 ^ a1
return calc_exp(6 + log[a1]) | (calc_exp(3 + log[a01]) << 16)
def mul_264(a, b):
if a == 0 or b == 0:
return 0
a0 = a & GF232_MASK
a1 = a >> 32
b0 = b & GF232_MASK
b1 = b >> 32
a01 = a0 ^ a1
b01 = b0 ^ b1
a0b0 = mul_232(a0, b0)
return (a0b0 ^ mul_by_231(mul_232(a1, b1))) | ((a0b0 ^ mul_232(a01, b01)) << 32)
def mul_232(a, b):
if a == 0 or b == 0:
return 0
a0 = a & GF216_MASK
a1 = a >> 16
b0 = b & GF216_MASK
b1 = b >> 16
a01 = a0 ^ a1
b01 = b0 ^ b1
a0b0 = mul_216(a0, b0)
return (a0b0 ^ calc_exp(3 + log[a1] + log[b1])) | (a0b0 ^ mul_216(a01, b01)) << 16
def mul_216(a, b):
if a == 0 or b == 0:
return 0
return calc_exp(log[a] + log[b])
def get_square(a):
a0 = a & GF216_MASK
a1 = (a >> 16) & GF216_MASK
a2 = (a >> 32) & GF216_MASK
a3 = a >> 48
return (square_table[0][a0] ^ square_table[1][a1] ^ square_table[2][a2] ^ square_table[3][a3])
def get_sqrt(a):
a0 = a & GF216_MASK
a1 = (a >> 16) & GF216_MASK
a2 = (a >> 32) & GF216_MASK
a3 = a >> 48
return (sqrt_table[0][a0] ^ sqrt_table[1][a1] ^ sqrt_table[2][a2] ^ sqrt_table[3][a3])
# Inverse functions
# (a0 + a1 * F) * (b0 + b1 * F) = 1
# <=> a0 * b0 + (a0 * b1 + a1 * b0) * F + a1 * b1 * F ** 2 = 1
# <=> a0 * b0 + (a0 * b1 + a1 * b0 + a1 * b1) * F + a1 * b1 * [F / 2] = 1
# a0 * b0 + a1 * b1 * [F / 2] = 1
# a1 * b1 = a0 * b1 + a1 * b0
# If we let d = (a0 * (a0 + a1) + a1 * a1 * [F / 2]) ** -1, and
# b0 = (a0 + a1) * d, b1 = a1 * d, then we can get the inverse of a.
# Proof: Try multiplying a and b!
def get_inv_216(a):
assert a != 0
return calc_exp(GF216_MASK - log[a])
def get_inv_232(a):
assert a != 0
a0 = a & GF216_MASK
a1 = a >> 16
a01 = a0 ^ a1
a2 = a ^ (a >> 16)
d = get_inv_216(mul_232(a, a2))
return mul_232(a2, d)
def get_inv_264(a):
assert a != 0
a0 = a & GF232_MASK
a1 = a >> 32
a01 = a0 ^ a1
a2 = a ^ (a >> 32)
d = get_inv_232(mul_264(a, a2))
return mul_264(a2, d)
# Solve the quadratic equation x ** 2 + x + a = 0.
# The polynomial f(x) = x ** 2 + x is a 2-to-1 mapping from GF(2 ** 16) to GF(2 ** 16).
# The range of f(x) is the set of all elements in GF(2 ** 16) with the 2 ** 15 bit off.
# Actually, with x in GF(F), if x ^ [F / 2] != 0, it still has a y that maps to x,
# but it is not in GF(F), it is in GF(F ** 2).
# Conversely, if x ^ [F / 2] = 0, then x has a y that maps to x in GF(F).
# Link: https://math.stackexchange.com/questions/3092194/quadratic-nimber-equation
# However, in the given functions, we will consider only the elements that have a preimage in GF(F).
# If we let a = a0 + a1 * F, then f^-1(a) = f^-1(a1) * F + f^-1(a1 ** 2 * [F / 2] + a0).
# Let b0 = a1 ** 2 * [F / 2] + a0.
# If b0 & [sqrt(F) / 2] = 0, then we can just use the function again.
# Else, we cannot, since b0 doesn't meet the condition of the function.
# But if we use Lemma 2 in the stackexchange link,
# If we let b0 = b1 + [sqrt(F) / 2], then f^-1(b0) = [sqrt(F)] + f^-1(b1).
def solve_quadratic_slow(prec, a):
if prec == 1:
assert a == 0
return 0
assert a >> (prec - 1) == 0
l = prec >> 1
a0 = a & ((1 << l) - 1)
a1 = a >> l
x1 = solve_quadratic_slow(l, a1)
b0 = a0 ^ mul_264(1 << (l - 1), get_square(x1))
s = b0 >> (l - 1)
return solve_quadratic_slow(l, b0 ^ s << (l - 1)) | (x1 ^ s) << l
def solve_quadratic(a):
assert a >> 63 == 0
a0 = a & GF216_MASK
a1 = (a >> 16) & GF216_MASK
a2 = (a >> 32) & GF216_MASK
a3 = a >> 48
return quad_inv_table[0][a0] ^ quad_inv_table[1][a1] ^ quad_inv_table[2][a2] ^ quad_inv_table[3][a3]
def is_solvable_quadratic(a, b):
return mul_264(get_inv_264(get_square(a)), b) >> 63 == 0
# solve quadratic x ** 2 + a * x + b = 0
# If we let t = x / a, then t ** 2 + t + b / a ** 2 = 0.
def solve_general_quadratic(a, b):
return mul_264(a, solve_quadratic(mul_264(get_inv_264(get_square(a)), b))) if a else get_sqrt(b)
def precompute_tables():
# Precompute exp and log tables
exp[0] = 1
for i in range(1, group_size - 1):
exp[i] = mul_slow(16, exp[i - 1], G16)
for i in range(group_size - 1, group_size * 2):
exp[i] = exp[i - group_size + 1]
log[0] = -10 ** 18
for i in range(group_size - 1):
log[exp[i]] = i
# Precompute square table
# (x + y) ** 2 = x ** 2 + y ** 2
# So, if we precompute square of all 16-bit numbers in a segment,
# we can get square, or sqrt of any 64-bit number by combining the results.
for s in range(64):
x = mul_264(1 << s, 1 << s)
for i in range(1 << (s & 15)):
square_table[s >> 4][i | 1 << (s & 15)] = square_table[s >> 4][i] ^ x
for s in range(64):
x = 1 << s
for _ in range(63):
x = get_square(x)
for i in range(1 << (s & 15)):
sqrt_table[s >> 4][i | 1 << (s & 15)] = sqrt_table[s >> 4][i] ^ x
for s in range(63):
x = solve_quadratic_slow(64, 1 << s)
for i in range(1 << (s & 15)):
quad_inv_table[s >> 4][i | 1 << (s & 15)] = quad_inv_table[s >> 4][i] ^ x
# Get the determinant of a matrix on the nimber field.
# This method uses Gaussian elimination to get the determinant.
def get_determinant(n, mat):
ans = 1
for i in range(n):
# Find a non-zero element in the i-th column
for j in range(i, n):
if mat[j][i]:
break
else:
return 0
for k in range(i, n):
mat[i][k], mat[j][k] = mat[j][k], mat[i][k]
ans = mul_264(ans, mat[i][i])
pivot_inv = get_inv_264(mat[i][i])
for j in range(i + 1, n):
if mat[j][i]:
ratio = mul_264(mat[j][i], pivot_inv)
for k in range(i, n):
mat[j][k] ^= mul_264(ratio, mat[i][k])
return ans
precompute_tables()
n = int(input())
matrix = [[*map(int, input().split())] for _ in range(n)]
if get_determinant(n, matrix):
print("First")
else:
print("Second")
詳細信息
Test #1:
score: 100
Accepted
time: 1221ms
memory: 48332kb
input:
3 0 1 2 1 2 3 1 2 1
output:
First
result:
ok Correct!
Test #2:
score: 0
Accepted
time: 1226ms
memory: 48296kb
input:
2 1 2 2 3
output:
Second
result:
ok Correct!
Test #3:
score: 0
Accepted
time: 1226ms
memory: 48304kb
input:
1 1
output:
First
result:
ok Correct!
Test #4:
score: 0
Accepted
time: 1229ms
memory: 48284kb
input:
1 0
output:
Second
result:
ok Correct!
Test #5:
score: 0
Accepted
time: 1235ms
memory: 48216kb
input:
1 10989383527054532353
output:
First
result:
ok Correct!
Test #6:
score: 0
Accepted
time: 1239ms
memory: 48380kb
input:
2 1005615900205140029 1751816340545810590 9799519860537995223 8238669462598964242
output:
First
result:
ok Correct!
Test #7:
score: 0
Accepted
time: 1227ms
memory: 48332kb
input:
2 14541323676997420853 9863599201339623558 7531150024641852914 12902197593218027764
output:
Second
result:
ok Correct!
Test #8:
score: 0
Accepted
time: 1248ms
memory: 48372kb
input:
5 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1
output:
First
result:
ok Correct!
Test #9:
score: 0
Accepted
time: 1232ms
memory: 48328kb
input:
7 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1
output:
First
result:
ok Correct!
Test #10:
score: 0
Accepted
time: 1232ms
memory: 48288kb
input:
8 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0
output:
Second
result:
ok Correct!
Test #11:
score: 0
Accepted
time: 1231ms
memory: 48364kb
input:
30 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1...
output:
Second
result:
ok Correct!
Test #12:
score: 0
Accepted
time: 1566ms
memory: 48640kb
input:
150 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 0 0 1 0 ...
output:
Second
result:
ok Correct!
Test #13:
score: 0
Accepted
time: 1561ms
memory: 48740kb
input:
150 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 ...
output:
First
result:
ok Correct!
Test #14:
score: 0
Accepted
time: 1227ms
memory: 48308kb
input:
6 1 0 3 3 1 0 0 2 3 0 1 3 1 1 3 1 3 3 3 0 0 3 2 0 3 1 3 1 3 0 1 2 3 0 1 0
output:
First
result:
ok Correct!
Test #15:
score: 0
Accepted
time: 1215ms
memory: 48304kb
input:
10 2 2 1 1 0 0 0 2 0 2 0 3 3 0 3 1 1 3 1 0 2 0 2 1 1 0 3 3 3 3 0 3 3 1 1 0 1 3 1 1 1 3 3 1 3 0 2 2 3 0 3 2 3 0 0 1 3 0 2 0 3 2 1 0 1 2 1 0 2 0 1 0 3 0 1 2 2 2 0 0 0 1 3 0 3 1 1 1 0 2 1 3 1 3 0 2 0 2 3 2
output:
Second
result:
ok Correct!
Test #16:
score: 0
Accepted
time: 1221ms
memory: 48380kb
input:
15 2 3 0 0 1 1 3 2 2 3 1 0 2 2 0 0 2 2 0 3 0 2 1 1 2 3 0 2 2 1 3 3 2 2 3 3 2 3 0 2 1 3 2 0 0 0 3 1 3 0 2 1 2 2 1 1 1 1 0 1 2 1 3 3 3 0 1 2 2 1 0 2 2 1 0 0 1 0 1 2 1 3 2 3 1 1 1 3 1 0 1 3 2 3 3 3 0 0 3 2 2 1 0 3 0 2 1 0 2 1 2 0 0 0 3 1 3 3 3 1 1 1 0 3 0 3 1 0 1 3 3 2 2 1 1 0 2 3 0 0 2 1 1 0 2 1 1 3 0...
output:
First
result:
ok Correct!
Test #17:
score: 0
Accepted
time: 1226ms
memory: 48328kb
input:
15 3 3 2 3 1 3 2 1 3 0 1 2 0 3 3 3 1 0 3 2 0 1 0 3 3 0 1 3 3 3 3 3 0 2 1 2 3 3 0 3 0 1 3 0 2 3 2 1 0 2 1 1 2 1 0 0 1 2 2 1 3 2 2 2 3 3 3 0 0 2 1 0 2 1 3 3 0 3 3 3 1 2 3 1 0 3 2 0 1 3 1 3 1 1 2 2 2 3 0 0 3 0 2 1 3 0 3 2 0 2 3 1 0 3 1 1 1 2 0 2 1 1 0 2 1 1 0 2 0 1 1 1 2 1 0 0 0 1 2 1 1 0 1 0 2 2 1 3 0...
output:
Second
result:
ok Correct!
Test #18:
score: -100
Time Limit Exceeded
input:
150 3 3 3 1 1 0 3 0 1 3 1 3 1 2 2 0 2 1 1 0 2 3 3 0 0 0 0 2 2 0 0 1 2 3 1 0 2 3 0 0 2 0 0 2 1 0 2 3 2 0 0 2 3 0 2 2 2 3 1 3 0 2 2 0 3 2 2 2 3 2 2 2 2 2 0 3 1 3 3 3 3 3 2 2 1 3 1 1 1 2 0 0 0 3 2 0 3 3 0 1 2 0 1 2 1 1 2 3 3 2 2 3 2 3 2 0 2 0 2 1 2 1 2 1 2 3 0 0 0 2 3 3 3 0 0 2 1 1 2 2 0 3 3 3 1 0 0 2 ...
output:
First