In [ ]:
def input():
# 2 1 2
return '''2 1 2
5 6 7'''.split('\n')
In [ ]:
def input():
# 2 1 2
return '''916989990 760860220 945427420'''.split('\n')
In [ ]:
from random import randint
m = long(1e9)
def input():
for _ in xrange(int(4)):
yield '{} {} {}'.format(randint(0, m + 1), randint(1, m + 1), randint(1, m + 1))
In [ ]:
mod = long(1e9 + 7)
def g(a, b):
if a == 0:
return b, 0, 1
else:
x, z, y = g(b % a, a)
return x, y - (b // a) * z, z
def i(a):
x, y, z = g(a % mod, mod)
if x != 1:
raise Exception('modular inverse does not exist, a = {}, x = {}'.format(a, x))
else:
return y % mod
def f(a, b, n):
def fi(p, q):
return (p * b + q * a) % mod, (q * b - p * a) % mod
def fm(p, q):
return (2 * p * q) % mod, (q**2 - p**2) % mod
if 1 == n:
return a, b
p, q = a, b;
z = []
while 0 < n:
z.append(0 == n % 2)
n /= 2
z = [zz for zz in reversed(z)][1:]
for zz in z:
p, q = fm(p, q)
if not zz:
p, q = fi(p, q)
return p, q
import sys
# sys.stdin.readline()
for line in input():
p, q, n = tuple(long(s) for s in line.split())
a, b = f(p, q, n)
binv = i(b)
r = (a * binv) % mod
print r
In [ ]:
a = 760860220
a * i(a) % mod
In [ ]:
def f(n):
if 1 == n:
return 1
x = 1;
z = []
while 0 < n:
z.append(0 == n % 2)
n /= 2
z = [zz for zz in reversed(z)][1:]
for zz in z:
x *= 2
if not zz:
x += 1
return x
for i in range(1, 100):
if i != f(i):
print "Error: ", i, f(i)
print [f(x) for x in range(1, 10)]
In [ ]:
import numpy as np
d = 2
# n * d**n -> + d**n + (n + 1) * d
# n -> + 1
# n + 1 -> + 1
# d**n -> * d
# d -> same
# 1 -> same
a = np.array([[d, d], # n * d**n -> * d -> + (d**n * d)
[0, d], # d**n -> * d
], dtype=np.int64)
print a
def f(n):
v = np.array([0, 1])
for _ in xrange(n):
v = np.dot(a, v)
return v
for i in xrange(5):
v = f(i)
print v
assert v[0] == i * d**i
assert v[1] == d**i
In [ ]:
import numpy as np
A = np.zeros((24, 24), dtype=np.int64)
# xn-10
# ...
# xn-1
# yn-10
# ...
# yn-1
# n * d**n
# d**n
# n * h**n
# h**n
for i in xrange(9):
xi = i
yi = i + 10
A[xi][xi + 1] = 1
A[yi][yi + 1] = 1
a = 1
b = 2
c = 3
A[9][10 - a] = 1
A[9][20 - b] = 1
A[9][20 - c] = 1
A[9][20 ] = 1
e = 2
f = 1
# g = 1
A[19][20 - e] = 1
A[19][10 - f] = 2
# A[19][10 - g] = 1
A[19][22 ] = 1
d = 2
A[20][20] = d
A[20][21] = d
A[21][21] = d
h = 4
A[22][22] = h
A[22][23] = h
A[23][23] = h
def f(n):
v = np.ones(24, dtype=np.int64)
v[20] = 0
v[22] = 0
for i in xrange(n):
v = np.dot(A, v)
v %= long(1e9)
return v
for n in xrange(12):
v = f(n)
print v[9], v[19]
In [ ]:
import numpy as np
def gen_A(a, b, c, d, e, f, g, h):
A = np.zeros((24, 24), dtype=np.int64)
for i in xrange(9):
xi = i
yi = i + 10
A[xi][xi + 1] = 1
A[yi][yi + 1] = 1
A[9][10 - a] = 1
if b == c:
A[9][20 - b] = 2
else:
A[9][20 - b] = 1
A[9][20 - c] = 1
A[9][20] = 1
A[19][20 - e] = 1
if f == g:
A[19][10 - f] = 2
else:
A[19][10 - f] = 1
A[19][10 - g] = 1
A[19][22] = 1
A[20][20] = d
A[20][21] = d
A[21][21] = d
A[22][22] = h
A[22][23] = h
A[23][23] = h
return A
def gen_v():
v = np.ones(24, dtype=np.int64)
v[20] = 0
v[22] = 0
return v
A = gen_A(1, 2, 3, 4, 5, 6, 7, 8)
def f(n):
v = gen_v()
for i in xrange(n):
v = np.dot(A, v)
v %= long(1e9)
return v
for n in xrange(12):
v = f(n)
print v[9], v[19]
In [1]:
def input():
# 2 1 2
return '''1 2 3 1 1 2 3 1 10
1 2 3 2 2 1 1 4 10
1 2 3 4 5 6 7 8 90'''.split('\n')
In [4]:
import numpy as np
def gen_A(a, b, c, d, e, f, g, h):
A = np.zeros((24, 24), dtype=np.int64)
for i in xrange(9):
xi = i
yi = i + 10
A[xi][xi + 1] = 1
A[yi][yi + 1] = 1
A[9][10 - a] = 1
if b == c:
A[9][20 - b] = 2
else:
A[9][20 - b] = 1
A[9][20 - c] = 1
A[9][20] = 1
A[19][20 - e] = 1
if f == g:
A[19][10 - f] = 2
else:
A[19][10 - f] = 1
A[19][10 - g] = 1
A[19][22] = 1
A[20][20] = d
A[20][21] = d
A[21][21] = d
A[22][22] = h
A[22][23] = h
A[23][23] = h
return A
def gen_v():
v = np.ones(24, dtype=np.int64)
v[20] = 0
v[22] = 0
return v
def f(A, n):
def fi(An):
r = np.dot(An, A)
r %= long(1e9)
return r
def fm(An):
r = np.dot(An, An)
r %= long(1e9)
return r
if 1 == n:
return An
z = []
while 0 < n:
z.append(0 == n % 2)
n /= 2
z = [zz for zz in reversed(z)][1:]
An = A.copy()
for zz in z:
An = fm(An)
if not zz:
An = fi(An)
v = gen_v()
r = np.dot(An, v)
r %= long(1e9)
return r
# sys.stdin.readline()
for line in input():
abc = tuple(int(s) for s in line.split())
A = gen_A(*abc[:-1])
n = abc[-1]
v = f(A, n + 1)
print v[9], v[19]
In [25]:
from copy import deepcopy
def dot(A, B, mod):
N = len(A)
M = len(B[0])
K = len(B)
assert K == len(A[0])
C = [[long(0)] * M for _ in xrange(N)]
for i in xrange(N):
for j in xrange(M):
for k in xrange(K):
C[i][j] += A[i][k] * B[k][j]
C[i][j] %= mod
return C
def trans(V):
N = len(V)
M = len(V[0])
U = [[long(0)] * N for _ in xrange(M)]
for i in xrange(N):
for j in xrange(M):
U[j][i] = V[i][j]
return U
def gen_A(a, b, c, d, e, f, g, h):
A = [[long(0)] * 24 for _ in xrange(24)]
for i in xrange(9):
xi = i
yi = i + 10
A[xi][xi + 1] = 1
A[yi][yi + 1] = 1
A[9][10 - a] = 1
if b == c:
A[9][20 - b] = 2
else:
A[9][20 - b] = 1
A[9][20 - c] = 1
A[9][20] = 1
A[19][20 - e] = 1
if f == g:
A[19][10 - f] = 2
else:
A[19][10 - f] = 1
A[19][10 - g] = 1
A[19][22] = 1
A[20][20] = d
A[20][21] = d
A[21][21] = d
A[22][22] = h
A[22][23] = h
A[23][23] = h
return A
def gen_v():
v = [long(1)] * 24
v[20] = 0
v[22] = 0
return trans([v])
def f(A, n):
def fi(An):
return dot(An, A, long(1e9))
def fm(An):
return dot(An, An, long(1e9))
if 1 == n:
return An
z = []
while 0 < n:
z.append(0 == n % 2)
n /= 2
z = [zz for zz in reversed(z)][1:]
An = deepcopy(A)
for zz in z:
An = fm(An)
if not zz:
An = fi(An)
return dot(An, gen_v(), long(1e9))
# sys.stdin.readline()
for line in input():
abc = tuple(int(s) for s in line.split())
A = gen_A(*abc[:-1])
n = abc[-1]
v = trans(f(A, n + 1))
print v[0][9], v[0][19]
In [26]:
def dot(A, B, mod):
N = len(A)
M = len(B[0])
K = len(B)
assert K == len(A[0])
C = [[long(0)] * M for _ in xrange(N)]
for i in xrange(N):
for j in xrange(M):
for k in xrange(K):
C[i][j] += A[i][k] * B[k][j]
C[i][j] %= mod
return C
def trans(V):
N = len(V)
M = len(V[0])
U = [[long(0) * N] for _ in xrange(M)]
for i in xrange(N):
for j in xrange(M):
U[j][i] = V[i][j]
return U
print dot([[1, 2],
[3, 4]],
[[5, 6],
[7, 8]], 100)
print dot([[1, 2, 3],
[4, 5, 6]],
[[7, 8],
[9, 10],
[11, 12]], 100)
print dot([[1, 2, 3],
[4, 5, 6]],
[[7], [8], [9]], 100)
print dot([[1, 2, 3],
[4, 5, 6]],
trans([[7, 8, 9]]), 100)
In [ ]: