3785 - AI

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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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()