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: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n, k = MI()
    aa = LLI(n)
    aa = np.array(aa,dtype="i8")
    ans = np.eye(n, dtype="i8")
    while k:
        if k & 1:
            np.dot(ans, aa, out=ans)
            ans%=md
        np.dot(aa, aa, out=aa)
        aa %= md
        k >>= 1
    #print(ans)
    print(np.sum(ans) % md)

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
G = [None] * N
for i in range(N):
    G[i] = LIST()
G = np.array(G, dtype=np.int64)

def mat_pow(mat, n, k):
    """ n*nの行列matを行列累乗でk乗する """

    res = np.zeros((n, n), dtype=np.int64)
    for i in range(n):
        res[i,i] = 1
    # 繰り返し二乗法
    while k > 0:
        if k & 1:
            res = np.dot(res, mat) % MOD
        mat = np.dot(mat, mat) % MOD
        k >>= 1
    return res

# 行列累乗でK項先へ
mat = mat_pow(G, N, K)

# グラフを行列としてK乗すれば、長さKのパスの総数が分かる(mat[i][j]=1で頂点i〜jが長さKのパスで繋がってる)
print(mat.sum()%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9+7
def MatPower(A, k):
    B = np.identity(len(A), dtype = object)
    while k:
        if k&1:
            B = np.dot(A, B)%mod
        A = np.dot(A, A)%mod
        k//=2
    return B
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype = object)
v = np.array([1]*N, dtype = object).T
An = MatPower(a, K)
v = np.dot(An, v)%mod
print(v.sum())

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9+7
def MatPower(A, k):
    B = np.identity(len(A), dtype = np.int64)
    while k:
        if k&1:
            B = np.dot(A, B)%mod
        A = np.dot(A, A)%mod
        k//=2
    return B
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype = np.int64)
v = np.array([1]*N, dtype = np.int64).T
An = MatPower(a, K)
v = np.dot(An, v)%mod
ans = 0
for i in range(N):
    ans+=v[i]
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 10**9+7
def MatPower(A, k):
    B = np.identity(len(A), dtype = np.int64)
    while k:
        if k&1:
            B = np.dot(A, B)%mod
        A = np.dot(A, A)%mod
        k//=2
    return B
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype = np.int64)
v = np.array([1]*N, dtype = np.int64).T
An = MatPower(a, K)
print((np.dot(An, v)%mod).sum()%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def power(b,p,f):
    """
    b: object (base)
    p: positive int (multiplier)
    f: multiple function
    return: f^p(b)
    """
    if not isinstance(p,int): raise ValueError("multiplier must be int")
    elif p<=0: raise ValueError("multiplier must be positive.")
    logp=p.bit_length()
    S=[0]*logp
    S[0]=b
    res='$'
    for i in range(logp):
        if i!=logp-1: S[i+1]=f(S[i],S[i])
        if p&(1<<i):
            if res=='$': res=S[i]
            else: res=f(res,S[i])
    return res

def mat_mul(A,B):
    assert len(A[0])==len(B)
    m=len(A)
    n=len(B)
    l=len(B[0])
    C=[[0]*l for _ in range(m)]
    for i in range(m):
        for j in range(l):
            for k in range(n):
                C[i][j]+=A[i][k]*B[k][j]
                C[i][j]%=MOD
    return C

def resolve():
    n,k=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(n)]
    dp=[[1]]*n
    A=power(A,k,mat_mul)
    dp=mat_mul(A,dp)
    res=0
    for i in range(n): res+=dp[i][0]
    print(res)
resolve()

Submission status: Wrong Answer

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 = 'int64')
A = A.T

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

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N, K = map(int, sys.stdin.readline().split())

dp = np.zeros((N,N), dtype='int64')

for i in range(N):
    dp[i] = np.array(list(map(int, sys.stdin.readline().split())))
    
n = dp.copy()
for i in range(K-1):
    dp = np.dot(dp, n)
    
print(sum(sum(dp)) / (1000000000 + 7))

Submission status: Wrong Answer

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(len(need[1:])):
    ##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: Wrong Answer

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]
for i in range(N):
    for j in range(N):
        start=dp[need[0]][i][j]
        for p in need[1:]:
            start*=dp[p][i][j]
            start%=MOD
        final_ans[i][j]=start
ans=0
for i in range(N):
    for j in range(N):
        ans+=final_ans[i][j]
        ans%=MOD
print(ans)

Submission status: Wrong Answer

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), int)
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: Wrong Answer

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), int)
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=np.int64)
#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: Wrong Answer

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), int)
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=np.int64)
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: Wrong Answer

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), int)
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=int)
i=1
while K:
  if K & 1:
    gridsave=np.dot(gridsave,grid) % MOD
  grid=np.dot(grid,grid) % MOD
  K>>=1
ans=np.sum(gridsave)%MOD
print(ans)

Submission status: Wrong Answer

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), int)
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: Wrong Answer

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="int64")
c = np.eye(n, dtype="int64")

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: Wrong Answer

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

Submission status: Wrong Answer

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=a**0
while k:b=b*a**(k&1);a=a*a%M;k>>=1
print(sum(b)%M)

Submission status: Wrong Answer

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**(k&1);a=a*a%M;k/=2
print sum(b)%M

Submission status: Wrong Answer

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))
while k:b=[b,b*a][k&1];a=a*a%M;k/=2
print sum(b)%M

Submission status: Wrong Answer

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])
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: Wrong Answer

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])
b=eye(n,n,0,int)
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)

Submission status: Wrong Answer

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],int)
b=eye(n,n,0,int)
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(sum(b)%M)

Submission status: Wrong Answer

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])
b=eye(n,n,0,int)
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(sum(b)%M)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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='i8')
b=numpy.eye(n,dtype='i8')
while k:
 if k&1:b=b*a%M
 a=a*a%M
 k>>=1
print(b.sum()%M)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), np.dtype('int64'))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM) % 1000000007
        if (d % 2 == 1):
            nM = nM.dot(M) % 1000000007
        return nM

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, np.dtype('int64'))
m = m.T
res = 0
a = myP(m, k).dot(np.ones(n, np.dtype('int64'))) % 1000000007
for i in a:
    res = (res + i) % 1000000007
print (res)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), np.dtype('int64'))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM) % 1000000007
        if (d % 2 == 1):
            nM = nM.dot(M) % 1000000007
        return nM

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, int)
m = m.T
res = 0
a = myP(m, k).dot(np.ones(n, np.dtype('int64'))) % 1000000007
for i in a:
    res = (res + i) % 1000000007
print (res)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), np.dtype('int64'))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM) % 1000000007
        if (d % 2 == 1):
            nM = nM.dot(m) % 1000000007
        return nM

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, int)
m = m.T
res = 0
a = myP(m, k).dot(np.ones(n, np.dtype('int64'))) % 1000000007
for i in a:
    res = (res + i) % 1000000007
print (res)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), np.dtype('int64'))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, int)
m = m.T
res = 0
a = myP(m, k).dot(np.ones(n, np.dtype('int64')))
for i in a:
    res = (res + i) % 1000000007
print (res)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), int)
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, int)
m = m.T
res = 0
a = myP(m, k).dot(np.ones(n, int))
for i in a:
    res = (res + i) % 1000000007
print (res)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), int)
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, int)
m = m.T
res = 0
a = myP(m, k).dot(np.ones(n, int))
for i in a:
    res += i
print (res)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.identity(len(M), int)
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m, int)
m = m.T
print (int(np.sum(myP(m, k).dot(np.ones(n, int)))))

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.eye(len(M))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
#print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m)
m = m.T
print (int(np.sum(myP(m, k).dot(np.ones(n))) % 1000000007 ))

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.eye(len(M))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m)
m = m.T
print (int(np.sum(myP(m, k).dot(np.ones(n))) % 1000000007 ))

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.eye(len(M))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

n, k = [int(x) for x in input().split()]
print(n, k)
m = []
for i in range(n):
    m.append([int(x) for x in input().split()])

m = np.array(m)
m = m.T
print (int(np.sum(myP(m, k).dot(np.ones(n)))) % 1000000007)

Submission status: Wrong Answer

Solution code:
def myP(M, d):
    if (d == 0):
        return np.eye(len(M))
    else:
        nM = myP(M, d // 2)
        nM = nM.dot(nM)
        if (d % 2 == 1):
            nM = nM.dot(m) 
        return nM % 1000000007

import numpy as np

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

m = np.array(m)
m = m.T
print (int(np.sum(myP(m, k).dot(np.ones(n)))))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
A=np.zeros((N,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]
x=K
T=A
ans=np.eye(N)
while x>0:
    if x%2==1:
        ans=np.dot(ans,T)
        ans%=mod
    T=np.dot(T,T)
    T%=mod
    x=x//2
num=0
for i in range(N):
    for j in range(N):
        num+=ans[i][j]
        num%=mod
print(int(num))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
A=np.zeros((N,N),dtype='int64')
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]
x=K
T=A
ans=np.eye(N,dtype='int64')
while x>0:
    if x%2==1:
        ans=np.dot(ans,T)
        ans%=mod
    T=np.dot(T,T)
    T%=mod
    x=x//2
num=0
for i in range(N):
    for j in range(N):
        num+=ans[i][j]
        num%=mod
print(int(num))

Submission status: Wrong Answer

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

import numpy as np
npA = np.array(A)

ans = 0
M = np.linalg.matrix_power(A, K)
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

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import numpy

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

S=numpy.matrix([1]*N,dtype="float128")
B=numpy.matrix(A,dtype="float128")

#ダブリング！

KDIG=[0]*60

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


for i in range(60):
    if KDIG[i]==1:
        S=S*B%mod
    
    B=B*B%mod

ANS=0
for i in range(N):
    ANS=(ANS+int(S[0,i]))%mod
print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy

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

S=numpy.matrix([1]*N,dtype="uint64")
B=numpy.matrix(A,dtype="uint64")

#ダブリング！

KDIG=[0]*60

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


for i in range(60):
    if KDIG[i]==1:
        S=S*B%mod
    
    B=B*B%mod

ANS=0
for i in range(N):
    ANS=(ANS+int(S[0,i]))%mod
print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy

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

S=numpy.matrix([1]*N,dtype="float128")
B=numpy.matrix(A,dtype="float128")

#ダブリング！

KDIG=[0]*70

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


for i in range(60):
    if KDIG[i]==1:
        S=S*B
        for j in range(N):
            S[0,j]=S[0,j]%mod
    
    B=B*B
    for j in range(N):
        for k in range(N):
            B[j,k]=B[j,k]%mod

ANS=0
for i in range(N):
    ANS=(ANS+int(S[0,i]))%mod
print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy

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

S=numpy.matrix([1]*N,dtype="int64")
B=numpy.matrix(A,dtype="int64")

#ダブリング！

KDIG=[0]*70

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


for i in range(70):
    if KDIG[i]==1:
        S=S*B
        for j in range(N):
            S[0,j]=S[0,j]%mod
    
    B=B*B
    for j in range(N):
        for k in range(N):
            B[j,k]=B[j,k]%mod

ANS=0
for i in range(N):
    ANS=(ANS+S[0,i])%mod
print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy

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

S=numpy.matrix([1]*N,dtype="int64")
B=numpy.matrix(A,dtype="int64")

#ダブリング！

KDIG=[0]*60

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


for i in range(60):
    if KDIG[i]==1:
        S=S*B
        for j in range(N):
            S[0,j]=S[0,j]%mod
    
    B=B*B
    for j in range(N):
        for k in range(N):
            B[j,k]=B[j,k]%mod

ANS=0
for i in range(N):
    ANS=(ANS+S[0,i])%mod
print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy

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

S=numpy.matrix([1]*N,dtype="int64")
B=numpy.matrix(A,dtype="int64")

#ダブリング！

KDIG=[0]*60

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


for i in range(60):
    if KDIG[i]==1:
        S=S*B
        for j in range(N):
            S[0,j]=S[0,j]%mod
    
    B=B*B
    for j in range(N):
        for k in range(N):
            B[j,k]=B[j,k]%mod

print(numpy.sum(S)%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
dp = np.array([list(map(int, input().split())) for _ in range(n)], dtype=np.int64)
ans = np.eye(n, dtype=np.int64)
MOD = 1000000007
while k:
    k, i = divmod(k, 2)
    if i:
        ans = np.mod(np.dot(ans, dp), MOD)
    dp = np.mod(np.dot(dp, dp), MOD)
print(sum(sum(a) % MOD for a in ans.tolist()) % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
dp = np.array([list(map(int, input().split())) for _ in range(n)], dtype=np.int64)
ans = np.eye(n, dtype=np.int64)
MOD = 1000000007
while k:
    k, i = divmod(k, 2)
    if i:
        ans = np.mod(np.dot(ans, dp), MOD)
    dp = np.mod(np.dot(dp, dp), MOD)
print(ans.sum() % MOD)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
import numpy as np
gyou = np.array(g).astype("int64")
ans = 0
while k>0:
  if k &1 ==1:
    if type(ans) is int:
      ans = gyou

      
    else:
      ans = np.dot(gyou,ans)      
  gyou = np.dot(gyou,gyou)
  k >>= 1
  ans %=mod
  gyou %= mod
print(np.sum(ans)%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
import numpy as np
gyou = np.array(g).astype("int64")
ans = np.eye(n).astype("int64")
while k:
  if k &1 ==1:
    ans = np.dot(gyou,ans)
  gyou = np.dot(gyou,gyou)
  k >>= 1
  ans %=mod
  gyou %= mod
kake = np.ones(n)
ans = np.dot(kake,ans).astype("int64")
print(np.sum(ans)%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
import numpy as np
gyou = np.array(g).astype("int64")
ans = np.eye(n).astype("int64")
while k:
  if k &1 ==1:
    ans = np.dot(ans,gyou)
  gyou = np.dot(gyou,gyou)
  k >>= 1
  ans %=mod
  gyou %= mod
print(np.sum(ans)%mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
g = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
import numpy as np
gyou = np.matrix(g)
ans = np.eye(n).astype(int)
ans = np.matrix(ans)
while k:
  if k &1 ==1:
    ans = np.dot(ans,gyou)
  gyou = np.dot(gyou,gyou)
  k >>= 1
  ans %=mod
  gyou %= mod
print(np.sum(ans)%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
A=np.zeros((N,N),dtype='uint64')
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]
x=K
T=A
ans=np.eye(N,dtype='uint64')
while x>0:
    if x%2==1:
        ans=np.dot(ans,T)
        ans%=mod
    T=np.dot(T,T)
    T%=mod
    x=x//2
num=0
for i in range(N):
    for j in range(N):
        num+=ans[i][j]
        num%=mod
print(int(num))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
A=np.zeros((N,N),dtype='uint64')
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]
x=K
T=A
ans=np.eye(N,dtype='uint64')
while x>0:
    if x%2==1:
        ans=np.dot(ans,T)
        ans%=mod
    T=np.dot(T,T)
    T%=mod
    x=x//2
num=0
for i in range(N):
    for j in range(N):
        num+=ans[i][j]
        num%=mod
print(num)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
A=np.zeros((N,N),dtype='int64')
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]
x=K
T=A
ans=np.eye(N,dtype='int64')
while x>0:
    if x%2==1:
        ans=np.dot(ans,T)
        ans%=mod
    T=np.dot(T,T)
    T%=mod
    x=x//2
num=0
for i in range(N):
    for j in range(N):
        num+=ans[i][j]
        num%=mod
print(num)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,K=map(int,input().split())
A=np.zeros((N,N),dtype='int64')
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]
x=K
T=A
ans=np.eye(N,dtype='int64')
while x>0:
    if x%2==1:
        ans=np.dot(ans,T)
        ans%=mod
    T=np.dot(T,T)
    T%=mod
    x=x//2
num=0
for i in range(N):
    num+=sum(ans[i])
    num%=mod
print(int(num))

Submission status: Wrong Answer

Solution code:
import numpy as np 
n, k = map(int, raw_input().split())
l = [map(int, raw_input().split()) for i in range(n)]
x = np.matrix(l)
x = x**k
print np.sum(x)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
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)