QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#553486 | #8095. Lati@s | ohwphil | TL | 1985ms | 48760kb | Python3 | 8.3kb | 2024-09-08 14:06:16 | 2024-09-08 14:06: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].
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")
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1223ms
memory: 48372kb
input:
3 0 1 2 1 2 3 1 2 1
output:
First
result:
ok Correct!
Test #2:
score: 0
Accepted
time: 1205ms
memory: 48344kb
input:
2 1 2 2 3
output:
Second
result:
ok Correct!
Test #3:
score: 0
Accepted
time: 1222ms
memory: 48300kb
input:
1 1
output:
First
result:
ok Correct!
Test #4:
score: 0
Accepted
time: 1224ms
memory: 48288kb
input:
1 0
output:
Second
result:
ok Correct!
Test #5:
score: 0
Accepted
time: 1217ms
memory: 48284kb
input:
1 10989383527054532353
output:
First
result:
ok Correct!
Test #6:
score: 0
Accepted
time: 1223ms
memory: 48356kb
input:
2 1005615900205140029 1751816340545810590 9799519860537995223 8238669462598964242
output:
First
result:
ok Correct!
Test #7:
score: 0
Accepted
time: 1241ms
memory: 48296kb
input:
2 14541323676997420853 9863599201339623558 7531150024641852914 12902197593218027764
output:
Second
result:
ok Correct!
Test #8:
score: 0
Accepted
time: 1208ms
memory: 48276kb
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: 1225ms
memory: 48268kb
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: 1204ms
memory: 48268kb
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: 1225ms
memory: 48272kb
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: 1540ms
memory: 48760kb
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: 1555ms
memory: 48640kb
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: 1212ms
memory: 48356kb
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: 1209ms
memory: 48372kb
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: 1237ms
memory: 48276kb
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: 1225ms
memory: 48264kb
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: 0
Accepted
time: 1985ms
memory: 48660kb
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
result:
ok Correct!
Test #19:
score: 0
Accepted
time: 1967ms
memory: 48680kb
input:
150 3 2 2 2 2 0 2 3 0 0 2 1 1 0 2 1 1 3 0 1 2 1 1 1 2 0 3 3 0 0 0 1 0 1 3 0 2 3 0 0 3 3 1 2 0 3 2 2 0 1 3 3 2 2 3 3 2 3 0 2 1 3 2 0 0 3 2 3 3 0 2 0 1 2 0 3 1 0 3 3 2 0 3 2 0 0 2 3 0 2 0 2 3 1 2 1 1 1 2 1 3 2 0 3 2 0 1 1 1 3 1 0 3 2 2 3 0 3 0 1 0 2 2 0 2 3 0 1 0 1 0 3 2 2 2 1 0 0 0 2 2 3 3 0 2 3 2 2 ...
output:
Second
result:
ok Correct!
Test #20:
score: 0
Accepted
time: 1224ms
memory: 48160kb
input:
4 14933869218549439491 16585424476599992641 15693327091049873813 15139317284981887413 5644635431761418741 14363600218451174558 6500511401460815337 15234460955132412106 7854875224242569311 14203824351831169222 17947187586523928667 17369385516825714001 7529062658482685749 6980600883025721660 866820821...
output:
First
result:
ok Correct!
Test #21:
score: 0
Accepted
time: 1214ms
memory: 48360kb
input:
6 1541940090421006634 5706980944228259629 3733156856506348515 11549906670735925984 3508919193506994963 12966245733830658096 16806498226151291947 7652725376596879919 10253139698466522875 5695783639911206394 856478020289437698 639981738440177442 1114326574664117727 10680210599297253080 755202771768002...
output:
Second
result:
ok Correct!
Test #22:
score: 0
Accepted
time: 1252ms
memory: 48248kb
input:
12 3357756343863405978 16086943693092603804 6300230423993775623 7972667015010053163 16179760515164929398 9948861293977891122 306236932643409121 9220435304801264449 1286640295606273752 7350687443474213116 16154223169996790543 10517646207801577965 7424542710891251074 4384550633238372902 12969678828580...
output:
First
result:
ok Correct!
Test #23:
score: 0
Accepted
time: 1216ms
memory: 48292kb
input:
13 9953705624019565478 1642510320265468085 4672511504386079306 18174598509365992760 13414653393975092944 2469051320651190720 3122286533861845469 10590394818949176522 15125046257771816999 7496919769199103511 2241705165090104491 11731906219134346173 11911485106014878064 967414319257420760 127564616926...
output:
Second
result:
ok Correct!
Test #24:
score: 0
Accepted
time: 1217ms
memory: 48176kb
input:
15 14263804391085055871 10189097583290923183 11855991718278251314 14709798954883622630 7478731964282786531 12484144778314696545 3362971101013729002 7931518435767573296 7920950763928225578 3419158813068432120 10128015810289738429 8364332849928439513 14830128233536617204 1539799100212387588 1030312448...
output:
Second
result:
ok Correct!
Test #25:
score: 0
Accepted
time: 1232ms
memory: 48272kb
input:
16 17359476782983281529 13082472111047927905 3150962834118022574 2600060412442128279 13694031871610209016 17565723700618907844 7891926568212661283 6946402817475122243 18038678885969164708 13221166522210591636 2985458790438500947 7829859654516566339 13762423062681684992 18091161409792617488 793780752...
output:
First
result:
ok Correct!
Test #26:
score: 0
Accepted
time: 1235ms
memory: 48292kb
input:
17 5317947837576302827 9328152479550380761 16455976998496880794 7522481156725147818 7872180946998333413 17124726256921772241 14514438975446359959 16255109669227189895 9583599332557166552 5530888402065577708 3003394442948264235 13984686417310107290 11895155396020519251 7138614150759090659 31255312984...
output:
Second
result:
ok Correct!
Test #27:
score: 0
Accepted
time: 1224ms
memory: 48296kb
input:
18 15399111227005505431 13038422771055042840 3475149860732507452 1249330319095171533 2241971710937880825 3349892092822803042 10427646873110937671 16269834369659997884 4256405874654164750 4820103298610498965 11274177702606438321 17096197564838891866 3736507591203397694 7128860710905751783 17072332102...
output:
First
result:
ok Correct!
Test #28:
score: 0
Accepted
time: 1251ms
memory: 48364kb
input:
30 14333479346300569793 155468631658949628 10787742168282851920 16097566594533678045 12159591562584644478 13861310319025912935 8313876318277202607 4252271325020573170 7223384252288614932 3196524622111763849 11128748277973967137 8562224680505924636 9461785526471315626 14667497891322652607 60574426812...
output:
First
result:
ok Correct!
Test #29:
score: 0
Accepted
time: 1560ms
memory: 48680kb
input:
70 14556674167334465063 8824345888529194640 12810176536470933801 3528198306054558224 17829225194625883641 4862672925370084742 10151979040623046761 4509929707338268910 17964651157020155758 14707151754130828670 10649554586486948534 11763141583292769016 16476282585787953076 17345561943741095840 1370364...
output:
Second
result:
ok Correct!
Test #30:
score: -100
Time Limit Exceeded
input:
100 727357525314754731 17753912689798219497 17806792077268193025 3352130942484431312 2826525390417635901 15817279169409766646 18374397388974452063 1415814498484392780 1367830964399943760 4790001893516129092 4890112977080693472 13717416443651253283 11212398728440477134 7447112388938555673 73661318761...