QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671140#9225. Fibonacci FusionLegend_dyRE 7ms10744kbPython31.5kb2024-10-24 11:12:222024-10-24 11:12:23

Judging History

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

  • [2024-10-24 11:12:23]
  • 评测
  • 测评结果:RE
  • 用时:7ms
  • 内存:10744kb
  • [2024-10-24 11:12:22]
  • 提交

answer

import math

sq5 = math.sqrt(5)

P = 1000000000000002097
fio = [0, 1]
for i in range(50):
    fio.append((fio[-1] + fio[-2]) % P)

def mul(m1, m2):
    m3 = [[0, 0], [0, 0]]
    for i in range(0, 2):
        for j in range(0, 2):
            for k in range(0, 2):
                m3[i][j] = (m3[i][j] + m1[i][k] * m2[k][j] % P) % P
    return m3

def Fio(n):
    if n <= 20:
        return fio[n]
    y = [[1, 0], [0, 1]]
    x = [[0, 1], [1, 1]]
    while n > 0:
        if n % 2 == 1:
            y = mul(y, x)
        x = mul(x, x)
        n //= 2
    return y[1][0]

def get(x):
    if x <= 20:
        y = 1
        while True:
            if fio[y] >= x:
                return y
            y += 1
    return math.ceil((math.log10(sq5) + math.log10(x)) / math.log10((1 + sq5) / 2))

n = int(input())
a = []
for i in range(0, n):
    a.append(int(input()))
# a.append(Fio(21) - 11)
# a.append(Fio(20) - 23)
# a.append(Fio(20) - 31)
# a.append(11)
# a.append(23)
# a.append(31)

a = sorted(a)

ans = 0

mp = {-1:0}

# k = get(10 ** 2000000)
# print(k)
# print(Fio(20))
# print(Fio(21))
for j in range(0, n):

    i = get(a[j])

    a[j] %= P
    ans += mp.get((Fio(i) - a[j] + P) % P, 0)
    ans += mp.get((Fio(i + 1) - a[j] + P) % P, 0)
    ans += mp.get((Fio(i + 2) - a[j] + P) % P, 0)
    ans += mp.get((Fio(i + 3) - a[j] + P) % P, 0)

    if mp.get(a[j], 0) == 0:
        mp.update({a[j]:1})
    else:
        mp[a[j]] += 1


print(ans)

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 10744kb

input:

6
50
8
8
5
72
354224848179261915070

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Dangerous Syscalls

input:

28
200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...

output:


result: