3785 - AI
De la Universitas MediaWiki
Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei E(n)=∑nk=1(2⋅(a2+b2)k2⋅cos(k⋅α)), unde α=arctg(ab) , iar n, a, b sunt numere naturale nenule.
Cerința
Să se afle valoarea expresiei , modulo 1.000.000.007
.
Date de intrare
Fișierul de intrare alIN.txt
conține pe prima linie numerele n, a, b
, separate prin spațiu.
Date de ieșire
Fișierul de ieșire alOUT.txt
va conține pe prima linie valoarea expresiei , modulo 1.000.000.007
.
Restricții și precizări
1 ≤ n ≤ 1012
1 ≤ a , b ≤ 20
Exemplul 1:
alIN.txt
3 5 12
alOUT.txt
1918
Explicatie
Dacă α=arctg(5/12), atunci sin(α)=5/13 şi cos(α)=12/13. Avem E(3)=2⋅13⋅cos(α)+2⋅13*2⋅cos(2α)+2⋅13*3⋅cos(3α)=2⋅13⋅12/13+2⋅13*2⋅(2⋅cos2(α)−1)+2⋅13*3⋅(4⋅cos*3(α)−3⋅cos(α))=24+238+1656=1918.
Exemplul 2:
alIN.txt
3 21 12
alOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
MOD = 1000000007
def gcd(a, b):
if b == 0:
return (1, 0)
else:
x, y = gcd(b, a % b)
return (y, x - y * (a // b))
def prod(x, y):
ret = [[0, 0], [0, 0]]
ret[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD
ret[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD
ret[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD
ret[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD
return ret
def pwr(mat, n):
nullMat = [[1, 0], [0, 1]]
if n == 0:
return nullMat
if n % 2:
return prod(mat, pwr(prod(mat, mat), n // 2))
return pwr(prod(mat, mat), n // 2)
def verify_restrictions(n, a, b):
if 1 <= n <= 1012 and 1 <= a <= 20 and 1 <= b <= 20:
return True
return False
def main():
try:
with open("alIN.txt", "r") as fin:
line = fin.readline().strip()
if not line:
raise ValueError("File is empty or invalid format.")
n, a, b = map(int, line.split())
if not verify_restrictions(n, a, b):
with open("alOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return
if n == 1:
E = ((a * a + b * b) * (2 * b - 2) - 2 * (b * b - a * a) + 2 * b) // (a * a + b * b - 2 * b + 1)
with open("alOUT.txt", "w") as fout:
fout.write(str(E))
return
numi = (b - 1) ** 2 + a * a
pat = a * a + b * b
invm, ins = gcd(numi, MOD)
initMat = [[2 * b, -pat], [1, 0]]
Alt = [[2 * (b * b - a * a), 0], [2 * b, 0]]
C = pwr(initMat, n - 1)
sol = prod(C, Alt)
En = -2 * pat + 2 * b
E = (pat * sol[1][0] - sol[0][0] + En) % MOD
E = (E * invm) % MOD
if E < 0:
E = (MOD + E) % MOD
with open("alOUT.txt", "w") as fout:
fout.write(str(E))
except Exception as e:
with open("alOUT.txt", "w") as fout:
fout.write(str(e))
if __name__ == "__main__":
main()