QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#553642#8095. Lati@sohwphilTL 1566ms48740kbPython38.4kb2024-09-08 17:03:192024-09-08 17:03:19

Judging History

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

  • [2024-09-08 17:03:19]
  • 评测
  • 测评结果:TL
  • 用时:1566ms
  • 内存:48740kb
  • [2024-09-08 17:03:19]
  • 提交

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

result: