Problem:


Score : 100 points

Problem Statement

There is a simple directed graph G with N vertices, numbered 1, 2, \ldots, N.

For each i and j (1 \leq i, j \leq N), you are given an integer a_{i, j} that represents whether there is a directed edge from Vertex i to j.
If a_{i, j} = 1, there is a directed edge from Vertex i to j; if a_{i, j} = 0, there is not.

Find the number of different directed paths of length K in G, modulo 10^9 + 7.
We will also count a path that traverses the same edge multiple times.

Constraints

All values in input are integers.

1 \leq N \leq 50

1 \leq K \leq 10^{18}

a_{i, j} is 0 or 1.

a_{i, i} = 0

Input

Input is given from Standard Input in the following format:

N K
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}

Output

Print the number of different directed paths of length K in G, modulo 10^9 + 7.

Sample Input 1

4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0

Sample Output 1

6

G is drawn in the figure below:

There are six directed paths of length 2:

1 → 2 → 3

1 → 2 → 4

2 → 3 → 4

2 → 4 → 1

3 → 4 → 1

4 → 1 → 2

Sample Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

G is drawn in the figure below:

There are three directed paths of length 3:

1 → 2 → 1 → 2

2 → 1 → 2 → 1

2 → 1 → 2 → 3

Sample Input 3

6 2
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0

Sample Output 3

1

G is drawn in the figure below:

There is one directed path of length 2:

4 → 5 → 6

Sample Input 4

1 1
0

Sample Output 4

0

Sample Input 5

10 1000000000000000000
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 0 1 1 0
0 1 1 1 0 1 0 1 1 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 0

Sample Output 5

957538352

Be sure to print the count modulo 10^9 + 7.



Sample input:
4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0


Sample output:
6

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7

def matmul(A,B,M): # A,B: 行列
    I,J,K = len(A), len(B[0]), len(B)  
    res = [[0] * J for _ in range(I)]
    for i in range(I):
        for k in range(K):
            for j in range(J):
                res[i][j] += A[i][k]*B[k][j]
                res[i][j] %= M
    return res

def matpow(A,p,M): #A^p mod M
    if p % 2:
        return matmul(A, matpow(A,p-1,M), M)
    elif p > 0:
        b = matpow(A, p//2, M)
        return matmul(b, b, M)
    else:
        return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]

#########################################################################################
#EDPC-R 

#########################################################################################

n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = matpow(A,k,MOD)
print(sum(sum(r) % MOD for r in ans) % MOD)

Submission status: Accepted

Solution code:
# @author 

import sys

class RWalk:
    def solve(self):

        MOD = 10 ** 9 + 7

        def mult(A, B):
            n, m, p = len(A), len(A[0]), len(B[0])
            assert(len(B) == m)
            C = [[0] * p for _ in range(n)]
            for i in range(n):
                for k in range(m):
                    a = A[i][k]
                    row = B[k]
                    for j in range(p):
                        C[i][j] = (C[i][j] + a * row[j]) % MOD

            return C

        def pow(A, k):
            n, m = len(A), len(A[0])
            if k == 0:
                return [[1 if i == j else 0 for j in range(m)] for i in range(n)]

            if k % 2 == 0:
                return pow(mult(A, A), k // 2)

            return mult(A, pow(A, k - 1))


        n, k = [int(_) for _ in input().split()]
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        print(sum([sum(line) for line in pow(a, k)]) % MOD)

solver = RWalk()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:

n, k = [ int(v) for v in input().split() ]
path_mat = [ [ int(v) for v in input().split() ] for i in range(n) ]

mod = 10**9+7

def mat_mul(inmat1,inmat2,m):
    outmat = [ [ 0 for j in range(m) ] for i in range(m) ]

    for i in range(m):
        for j in range(m):
            for g in range(m):
                outmat[i][j] += inmat1[i][g] * inmat2[g][j]
            outmat[i][j] %= mod
    return outmat


ans_mat = [ [ 1 if i == j else 0 for j in range(n) ] for i in range(n) ]

while k != 0:
    if k % 2 == 1:
        ans_mat = mat_mul(ans_mat,path_mat,n)
    k = k // 2
    path_mat = mat_mul(path_mat,path_mat,n)
    

print(sum([ sum(i) for i in ans_mat ])%mod)

Submission status: Accepted

Solution code:
import numpy as np

N, K = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(N)]
MOD = 10 ** 9 + 7

A = np.array(a, dtype = 'O')
A = A.T

ans = np.eye(N, dtype = 'O')
while K:
  if K & 1:
    ans = np.dot(ans, A)
    ans %= MOD
  A = np.dot(A, A)
  A %= MOD
  K >>= 1

print(np.sum(abs(ans)) % MOD)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7
N,K = map(int,input().split())
A = np.array([input().split() for _ in range(N)],dtype=np.int64)

def mult1(A,B):
    C = np.zeros_like(A)
    for i in range(N):
        for j in range(N):
            C[i,j] = (A[i,:] * B[:,j] % MOD).sum() % MOD
    return C

def mult(A,B):
    # 桁あふれ回避のため
    M = 1 << 16
    A1,A2 = A//M,A%M
    B1,B2 = B//M,B%M
    X,Y,Z = (np.dot(P,Q) % MOD for P,Q in ((A1,B1),(A1-A2,B1-B2),(A2,B2)))
    return ((X << 32) + (X+Z-Y << 16) + Z) % MOD

def power(A,k):
    if k == 1:
        return A
    X = power(A,k//2)
    X = mult(X,X)
    return mult(A,X) if k&1 else X

answer = power(A,K).sum() % MOD
print(answer)

Submission status: Accepted

Solution code:
N,K=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(N):
    A+=[list(map(int,input().strip().split(' ')))]
dic={}
MOD=10**9+7
power=1
while 2**power<=K:
    power+=1

dp=[[[0 for j in range(N)] for i in range(N)] for p in range(power+1) ]
for p in range(0,power+1):
    
    if p==0:
        for i in range(N):
            for j in range(N):
                if A[i][j]==1:
                    dp[p][i][j]=1
    else:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[p][i][j]+=(dp[p-1][i][k]*dp[p-1][k][j])%MOD
                    dp[p][i][j]%=MOD

    
rep=bin(K)[2:][::-1]
final_ans=[[0 for i in range(N)] for j in range(N)]
need=[]
for i in range(len(rep)):
    if rep[i]=="1":
        need+=[i]

final=[[dp[need[0]][i][j] for j in range(N)] for i in range(N)]
for i in range(1,len(need)):
    ##start*dp[need[i]]
    temp_ans=[[0 for i in range(N)] for j in range(N)]
    for x in range(N):
        for y in range(N):
            temp=0
            for z in range(N):
                temp+=final[x][z]*dp[need[i]][z][y]
                temp%=MOD
            temp_ans[x][y]=temp
    final=[[temp_ans[i][j] for j in range(N)] for i in range(N)]
            
ans=0
for i in range(N):
    for j in range(N):
        ans+=final[i][j]
        ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

MOD=10**9+7
N, K = map(int, input().split())
grid = np.empty((0,N), dtype='O')
for i in range(N):
  array = list(map(int, input().strip().split()))
  array2 = np.array(array)
  grid = np.append(grid,[array2],axis=0)
#print(grid)
dp=[[grid]]
gridsave=grid
i=1
while 2**i<=K:
  #print(i)
  #dp.insert(1,grid*grid)
  gridsave=np.dot(dp[i-1][0],dp[i-1][0])
  gridsave=np.mod(gridsave,MOD)
  #print(gridsave)
  dp.append([gridsave])
  i+=1
i-=1
K-=2**i
i-=1
#print('dp',dp)
grid1=dp[len(dp)-1][0]
#print(grid1)
#print(i)
while K>0:
  if K>=2**i:
    #print('i',i)
    grid1=np.dot(grid1,dp[i][0])
    grid1=np.mod(grid1,MOD)
    K-=2**i
    #print('grid1',grid1)
  i-=1
  #print('K',K)
ans=0
#print(grid1)
for i in range(N):
  for j in range(N):
    ans=(ans+grid1[i][j])%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

MOD=10**9+7
N, K = map(int, input().split())
grid = np.empty((0,N), dtype='O')
for i in range(N):
  array = list(map(int, input().strip().split()))
  array2 = np.array(array)
  grid = np.append(grid,[array2],axis=0)
#print(grid)
dp=[[grid]]
gridsave=np.eye(N,dtype="O")
#print(gridsave)
i=1
while K:
  if K & 1:
    gridsave=np.dot(grid,gridsave) % MOD
  grid=np.dot(grid,grid) % MOD
  K>>=1
ans=np.sum(gridsave)%MOD
#print(gridsave)
print(ans)

Submission status: Accepted

Solution code:
def mat_dot(A, B, mod):
    assert len(A[0]) == len(B), 'invalid_size'
    
    L = len(A)
    M = len(A[0])
    N = len(B[0])
    
    res = [[0]*N for _ in range(L)]
    
    for i in range(L):
        for j in range(N):
            a = 0
            for k in range(M):
                a = (a+A[i][k]*B[k][j]) % mod
            res[i][j] = a
            
    return res

def mat_pow(A, x, mod):
    N = len(A)
    res = [[0]*N for _ in range(N)]
    for i in range(N):
        res[i][i] = 1
    for i in range(x.bit_length()):
        if 2**i & x:
            res = mat_dot(res, A, mod)
        A = mat_dot(A, A, mod)
    return res

N, K = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(N)]
A = list(map(list, zip(*A)))
mod = 10**9+7
B = mat_pow(A, K, mod)
ans = 0
for i in range(N):
    for j in range(N):
        ans = (ans + B[i][j]) % mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7

def matmul(A, B, mod): # A,B: 行列
    res = [[0] * len(B[0]) for _ in range(len(A))]
    for i, resi in enumerate(res):
        for k, aik in enumerate(A[i]):
            for j,bkj in enumerate(B[k]):
                resi[j] += aik*bkj
                resi[j] %= mod
    return res

def matpow(A, p, M): #A^p mod M
    if p % 2 == 1:
        return matmul(A, matpow(A, p - 1, M), M)
    elif p > 0:
        b = matpow(A, p // 2, M)
        return matmul(b, b, M)
    else:
        return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = matpow(A,k,MOD)
print(sum(sum(r) % MOD for r in ans) % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7

def dot(a, b):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k, aik in enumerate(a[i]):
            for j,bkj in enumerate(b[k]):
                res[i][j] += aik*bkj
                res[i][j] %= MOD
    return res


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = [[0] * n for _ in range(n)]
for i in range(n):
    ans[i][i] = 1

while k:
    k, i = divmod(k, 2)
    if i:
        ans = dot(ans, A)
    A = dot(A, A)

res = 0
for i in range(n):
  for j in range(n):
    res += ans[i][j]
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7

def dot(a, b):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k, aik in enumerate(a[i]):
            for j,bkj in enumerate(b[k]):
                res[i][j] += aik*bkj
                res[i][j] %= MOD
 
    return res


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = [[0] * n for _ in range(n)]
for i in range(n):
    ans[i][i] = 1

while k:
    k, i = divmod(k, 2)
    if i:
        ans = dot(ans, A)
    A = dot(A, A)

print(sum(sum(A) % MOD for A in ans) % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
dp = [list(map(int, input().split())) for i in range(n)]
MOD = 10**9 + 7

def _mul(A, B, MOD):
    C = [[0] * len(B[0]) for i in range(len(A))]
    for i in range(len(A)):
        for k in range(len(B)):
            for j in range(len(B[0])):
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
    return C

#A**n
def pow(A, n, MOD):
    B = [[0] * len(A) for i in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1
    while n > 0:
        if n & 1:
            B = _mul(A, B, MOD)
        A = _mul(A, A, MOD)
        n  = n // 2
    return B

ans_matrix = pow(dp, k, MOD)
ans = 0
for i in range(n):
    ans += sum(ans_matrix[i])
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys

input = sys.stdin.readline

md = 10 ** 9 + 7
n, k = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(n)], dtype="O")
c = np.eye(n, dtype="O")

while k:
    if k & 1:
        c = np.dot(a, c) % md
    a = np.dot(a, a) % md
    k >>= 1
print(np.sum(c) % md)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def dot(a, b):
    c = [[0] * n for _ in range(n)]
    for i, ai in enumerate(a):
        for j, bj in enumerate(zip(*b)):
            c[i][j] = sum(ak * bk for ak, bk in zip(ai, bj)) % md
    return c


def pwr(a, k):
    c = None
    while c == None:
        if k & 1:
            c = a
        a = dot(a, a)
        k >>= 1

    while k > 0:
        if k & 1:
            c = dot(a, c)
        a = dot(a, a)
        k >>= 1
    return c


md = 10 ** 9 + 7
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(sum([sum(pk) % md for pk in pwr(a, k)]) % md)

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda*z:map(int,raw_input().split())
n,k=m()
b=[1]*n
a=matrix(map(m,b),'O')
while k:b*=[1,a][k&1];a=a*a%M;k/=2
print sum(b)%M

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda*z:map(int,raw_input().split())
n,k=m()
b=[1]*n
a=matrix(map(m,b),'O')
while k:b=[b,b*a][k&1];a=a*a%M;k/=2
print sum(b)%M

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,raw_input().split())
n,k=m()
b=eye(n,n,0,'O')
a=matrix([m()for i in b],'O')
while k:b,a=[b,b*a][k&1],a*a%M;k/=2
print sum(b)%M

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda*z:map(int,raw_input().split())
n,k=m()
b=eye(n,n,0,'O')
a=matrix(map(m,b),'O')
while k:b=[b,b*a][k&1];a=a*a%M;k/=2
print sum(b)%M

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,raw_input().split())
n,k=m()
b=eye(n,n,0,'O')
a=matrix([m()for i in b],'O')
while k:b=[b,b*a][k&1];a=a*a%M;k/=2
print sum(b)%M

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,raw_input().split())
n,k=m()
b=eye(n,n,0,'O')
a=matrix([m()for i in b],'O')
while k:b=[b,b*a][k&1];a=a*a%M;k>>=1
print sum(b)%M

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
b=eye(n,n,0,'O')
a=matrix([list(m())for i in b],'O')
while k:b=[b,b*a][k&1];a=a*a%M;k>>=1
print(sum(b)%M)

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=matrix([list(m())for i in[0]*n],'O')
b=eye(n,n,0,'O')
while k:b=[b,b*a][k&1];a=a*a%M;k>>=1
print(sum(b)%M)

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=matrix([list(m())for i in[0]*n],'O')
b=eye(n,n,0,'O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(sum(b)%M)

Submission status: Accepted

Solution code:
from numpy import*
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=matrix([list(m())for i in[0]*n],'O')
b=eye(n,n,0,'O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy as P
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=P.matrix([list(m())for _ in[0]*n],dtype='O')
b=P.eye(n,n,0,'O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy as P
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=P.matrix([list(m())for i in[0]*n],'O')
b=P.eye(n,n,0,'O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy as P
M=10**9+7
n,k=map(int,input().split())
a=P.matrix([list(map(int,input().split()))for i in[0]*n],'O')
b=P.eye(n,n,0,'O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy as P
M=10**9+7
m=lambda:map(int,input().split())
n,k=m()
a=P.matrix([list(m())for _ in[0]*n],dtype='O')
b=P.eye(n,dtype='O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy as P
M=10**9+7
n,k=map(int,input().split())
a=P.matrix([list(map(int,input().split()))for i in[0]*n],dtype='O')
b=P.eye(n,dtype='O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy
M=10**9+7
n,k=map(int,input().split())
a=numpy.matrix([list(map(int,input().split()))for i in[0]*n],dtype='O')
b=numpy.eye(n,dtype='O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy as P
M=10**9+7
n,k=map(int,input().split())
a=P.matrix([list(map(int,input().split()))for i in[0]*n],dtype='O')
b=P.eye(n,dtype='O')
while k:
 if k&1:b=b*a%M
 a=a*a%M
 k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
import numpy
M=10**9+7
n,k=map(int,raw_input().split())
a=numpy.matrix([map(int,raw_input().split())for i in[0]*n],dtype='O')
b=numpy.eye(n,dtype='O')
while k:
 if k&1:b=b*a%M
 a=a*a%M
 k/=2
print b.sum()%M

Submission status: Accepted

Solution code:
import numpy
M=10**9+7
n,k=map(int,input().split())
a=numpy.matrix([list(map(int,input().split()))for i in[0]*n],dtype='O')
b=numpy.eye(n,dtype='O')
while k:
 if k&1:b=b*a%M
 a=a*a%M
 k>>=1
print(b.sum()%M)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(N, K, A):
    m = [[0] * N for _ in range(N)]
    for i in range(N):
        m[i][i] = 1
    k = K
    a = A

    def mulmod(a, b):
        m = [[0] * N for _ in range(N)]
        for i, r, in enumerate(a):
            for j, c in enumerate(zip(*b)):
                m[i][j] = sum(x * y for x, y in zip(r, c)) % mod
        return(m)

    while k > 0:
        if k & 1:
            m = mulmod(m, a)
        a = mulmod(a, a)
        k >>= 1

    return(sum(sum(x) for x in m) % mod)

N, K = map(int, input().split()) # 1 <= N <= 50, 1 <= K <= 10^18
a = [list(map(int, input().split())) for _ in range(N)]

print(f(N, K, a))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
mod=10**9+7

def MatMul(A,B):
    C=[[0]*len(B[0]) for _ in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                C[i][j]+=A[i][k]*B[k][j]
                C[i][j]%=mod
    return C
def MatPow(A,n):
    l=len(A)
    B=[[0]*l for _ in range(l)]
    for i in range(l):
        B[i][i]=1
    while n:
        if n&1:
            B=MatMul(B,A)
        A=MatMul(A,A)
        n//=2
    return B

n,k=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(n)]
P=MatPow(A,k)
ans=0
for p in P:
    ans+=sum(p)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:


MOD = 1000000007


def mult(a, b):
    c = [[0] * len(a) for _ in range(len(a))]
    for i in range(len(a)):
        for j in range(len(a)):
            for k in range(len(a)):
                c[i][j] += a[i][k] * b[k][j] % MOD
                c[i][j] %= MOD
    return c

def power(a, n):
    p = [[0] * len(a) for _ in range(len(a))]
    for i in range(len(a)):
        p[i][i] = 1

    while n:
        if n % 2:
            p = mult(p, a)
        a = mult(a, a)
        n /= 2
    return p

n, k = map(int, raw_input().split())
graph = []
for i in range(n):
    graph.append(map(int, raw_input().split()))
graph = power(graph, k)
resp = 0
for r in graph:
    resp += sum(r)
    resp %= MOD
print(resp)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,K = map(int, input().split())
A = [ [int(j) for j in input().split()] for i in range(N)]
# I = [ [j for j in range(1,N+1) if Ai[j]] for Ai in A]
MOD = 10**9 + 7

# dp = [0] * (N+1)
dp = [ [0] * (N+1) for _ in range(N+1)]

S = [[1]*N]
KDIG = [0]*70

for i in range(1,61):
    if K % (1<<i) :
        KDIG[i-1] = 1
        K -= K%(1<<i)


def prod(A,B,k,l,m):#A:k*l,B:l*m
 
    C=[[None for i in range(m)] for j in range(k)]
 
    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])%MOD
 
            C[i][j]=ANS
 
    return C



for i in range(60):
    if KDIG[i] == 1:
        S = prod(S,A,1,N,N)

    A = prod(A,A,N,N,N)
print(sum(S[0])%MOD)

# for i in range(1,N+1):
#     for j in range(1,N+1):
#         # dp[i][j] = np.linalg.matrix_power(A, K)[i-1][j-1].item()
#         # ans += dp[i][j] % MOD
#         # ans += np.linalg.matrix_power(A, K)[i-1][j-1].item() % MOD
#         # ans += M[i-1,j-1].item() % MOD
#         ans += M[i-1][j-1] % MOD

# print(ans%MOD)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

S=[[1]*N]
KDIG=[0]*70

for i in range(1,61):
    if K%(1<<i):
        KDIG[i-1]=1
        K-=K%(1<<i)

def prod(A,B,k,l,m):#A:k*l,B:l*m

    C=[[None for i in range(m)] for j in range(k)]

    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])%mod

            C[i][j]=ANS

    return C

for i in range(60):
    if KDIG[i]==1:
        S=prod(S,A,1,N,N)
    
    A=prod(A,A,N,N,N)

print(sum(S[0])%mod)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]
MOD = 10**9+7

def mul(L,R):
    ret = [[0]*N for _ in range(N)]
    for i,row in enumerate(L):
        for j,col in enumerate(zip(*R)):
            ret[i][j] = sum(a*b for a,b in zip(row,col)) % MOD
    return ret

M = A
Z = [[int(i==j) for j in range(N)] for i in range(N)]
while K:
    if K%2:
        Z = mul(Z,M)
    M = mul(M,M)
    K //= 2

print(sum(sum(row) for row in Z) % MOD)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Matrix():
    def __init__(self, A):
        self.A = A
        self.row = len(A)
        self.col = len(A[0])

    def __iter__(self):
        return self.A.__iter__()

    def __getitem__(self, i):
        return self.A.__getitem__(i)

    def __add__(self, B):
        aa = self.A
        bb = B.A
        return Matrix([[aa[i][j] + bb[i][j] for j in range(self.col)] for i in range(self.row)])

    def __sub__(self, B):
        aa = self.A
        bb = B.A
        return Matrix([[aa[i][j] - bb[i][j] for j in range(self.col)] for i in range(self.row)])

    def __mul__(self, B):
        bb = [[B.A[j][i] for j in range(B.row)] for i in range(B.col)]
        return Matrix([[sum([ak * bk for ak,bk in zip(ai,bj)]) % mod for bj in bb] for ai in self.A])

    def __truediv__(self, x):
        pass

    def pow(self, n):
        A = self
        r = Matrix([[0 if j != i else 1 for j in range(self.row)] for i in range(self.row)])
        while n > 0:
            if n % 2 == 1:
                r = r * A
            A = A * A
            n //= 2
        return r

    def lu(self):
        # squarenのみ
        size = self.row
        T = copy.deepcopy(self.A)
        L = [[0]*size for _ in range(size)]
        U = [[0]*size for _ in range(size)]
        for i in range(size):
            for j in range(i,size):
                L[j][i] = T[j][i]
            for j in range(i,size):
                U[i][j] = T[i][j] / T[i][i]
            for j in range(i+1,size):
                for k in range(i+1,size):
                    T[j][k] -= L[j][i] * U[i][k]

        return Matrix(L),Matrix(U)

    def __str__(self):
        return self.A.__str__()


def main():
    n,k = LI()
    a = [LI() for _ in range(n)]
    A = Matrix(a)
    P = A.pow(k)

    return sum(map(sum,P.A)) % mod


print(main())

Submission status: Accepted

Solution code:
def dot(a, b):
    ret = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            ret[i][j] = sum(a[i][k] * b[k][j] for k in range(n)) % MOD
    return ret


n, k = map(int, input().split())
dp = [list(map(int, input().split())) for _ in range(n)]
ans = [[0] * n for _ in range(n)]
for i in range(n):
    ans[i][i] = 1
MOD = 1000000007
while k:
    k, i = divmod(k, 2)
    if i:
        ans = dot(ans, dp)
    dp = dot(dp, dp)
print(sum(sum(a) % MOD for a in ans) % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def mul(A, B):
    return [[sum(A[i][k] * B[k][j] for k in range(N)) % MOD for j in range(N)] for i in range(N)]

N, K = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]

R = [[i==j for i in range(N)] for j in range(N)]
while K:
    if K & 1:
        R = mul(R, A)
    A = mul(A, A)
    K >>= 1
print(sum(sum(r) for r in R) % MOD)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
ans = 0
def mul(x,y):
  res = []
  for i in range(n):
    tmp = []
    for j in range(n):
      ko = 0
      for k in range(n):
        ko += x[i][k] * y[k][j]
        ko %=mod
      tmp.append(ko)
    res.append(tmp)
  return res
while k>0:
  if k &1 ==1:
    if type(ans) is int:
      ans = g
    else:
      ans = mul(g,ans)
  g = mul(g,g)
  k >>= 1
res = 0
for i in range(n):
  for j in range(n):
    res += ans[i][j]
    res %= mod
print(res)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [[0] * N for i in range(N)]
mod = 10 ** 9 + 7
for i in range(N):
    B = [int(i) for i in input().split()]
    for j in range(N):
        A[i][j] = B[j]


def dot(X, Y):
    Z = [[0] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            t = 0
            for k in range(N):
                t += X[i][k] * Y[k][j]
                t %= mod
            Z[i][j] = t
    return Z

#print(A)
x = K
T = A
ans = [[0]*N for i in range(N)]
for i in range(N):
    ans[i][i]=1
while x > 0:
    if x % 2 == 1:
        ans = dot(ans, T)
    T = dot(T, T)
    #print(T)
    x = x // 2
num = 0
for i in range(N):
    num += sum(ans[i])
    num %= mod
print(num)
#print(ans)

Submission status: Runtime Error

Solution code:
def mult(A, B):
    C = [[0 for i in range(len(A))] for i in range(len(A))]
 
    for i in range(len(A)):
        for j in range(len(A)):
            for k in range(len(A)):
                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%mod
    
    return C
 
def exp(A, p):
    ans = [[0 for i in range(len(A))] for i in range(len(A))]
    for i in range(len(A)):
        ans[i][i] = 1
    
    while p:
        if p%2 == 0:
            A = mult(A, A)
            p = p//2
        else:
            ans = mult(ans, A)
            p -= 1
    
    return ans
 
n, k = map(int, input().strip().split())
grid = [list(map(int, input().strip().split())) for i in range(n)]
 
print(sum([sum(i)%mod for i in exp(grid, k)])%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(N)]
a=np.array(a,dtype=np.int64)
MOD=10**9+7

def matmul(A,B,MOD):
    N=len(A)
    C=np.zeros((N,N),dtype=np.int64)

    for n in range(N):
        C[n] = (A[n,:][:,None] * B % mod).sum(axis=0) % mod
    return C

def mat_power(A,k,MOD):
    N=len(A)
    D=np.identity(N,dtype=np.int64)
    while k:
        if k & 1:
            D=matmul(D,A,MOD)
        A = matmul(A,A,MOD)
        k >>= 1

    return D

A=mat_power(a,K,MOD)
ans=0
for i in range(N):
    for j in range(N):
        ans=(ans+A[i][j])%MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(N)]
a=np.array(a,dtype=np.int64)
MOD=10**9+7

def matmul(A,B,MOD):
    N=len(A)
    C=np.zeros(N,dtype=np.int64)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i][j] += A[i][k]*B[k][j]%MOD
    return C

def mat_power(A,k,MOD):
    N=len(A)
    D=np.identity(N,dtype=np.int64)
    while k:
        if k & 1:
            D=matmul(D,A,MOD)
        A = matmul(A,A,MOD)
        k >>= 1

    return D

A=mat_power(a,K,MOD)
ans=0
for i in range(N):
    for j in range(N):
        ans=(ans+A[i][j])%MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,K=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(N)]
a=np.array(a,dtype=np.int64)
MOD=10**9+7

def matmul(A,B,MOD):
    N=len(A)
    C=np.zeros(N,dtype=np.int64)
    for i in range(N):
        for j in range(N):
            for k in range(N):
            C[i][j] += A[i][k]B[k][j]%MOD
    return C

def mat_power(A,k,MOD):
    N=len(A)
    D=np.identity(N,dtype=np.int64)
    while k:
        if k & 1:
            D=matmul(D,A,MOD)
        A = matmul(A,A,MOD)
        k >>= 1

    return D

A=mat_power(a,K,MOD)
ans=0
for i in range(N):
    for j in range(N):
        ans=(ans+A[i][j])%MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N,K=map(int,input().split())
A = np.array([list(map(int,input().split())) for _ in range(N)],dtype=int)
mod = 10**9+7

res = matrix_power(A,N,mod)
print(res.sum()%mod)

power_list=[A]
for i in range(1,K.bit_length()+1):
  power_list.append((power_list[-1]@power_list[-1])%mod)
  
B = np.identity(N).astype(int)
for i in range(K.bit_length()+1):
  if K>>i&1:
    B = (B @ power_list[i])%mod

print(B.sum()%mod)

Submission status: Runtime Error

Solution code:
from numpy import int_

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())
A = int_(A).reshape(N, N)

K //= 2
ans = A
while K:
    if K & 1:
        ans = (ans @ A) % mod
    A = (A @ A) % mod
    K //= 2

print(ans.sum())