QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#553486#8095. Lati@sohwphilTL 1985ms48760kbPython38.3kb2024-09-08 14:06:162024-09-08 14:06:19

Judging History

你现在查看的是最新测评结果

  • [2024-09-08 14:06:19]
  • 评测
  • 测评结果:TL
  • 用时:1985ms
  • 内存:48760kb
  • [2024-09-08 14:06:16]
  • 提交

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...

output:


result: