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: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w=map(int,input().split())
    A=[input() for _ in range(h)]
    dp=[[0]*w for _ in range(h)] #(i,j)までの経路の総数
    dp[0][0]=1
    mod=10**9+7
    for i in range(h):
        for j in range(w):
            if A[i][j]=="#":continue
            if i>=1 and j>=1:    
                dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%mod
            elif j==0:
                dp[i][j]+=dp[i-1][j]%mod
            else:
                dp[i][j]+=dp[i][j-1]%mod
    print(dp[-1][-1]%mod)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
Edge = [[] for __ in range(N)]
ans = 0
mod = 10**9 + 7

for i in range(N):
    a = list(map(int, input().split()))
    for j in range(N):
        if a[j]:
            Edge[i].append(j)

DP = [[0] * (K+1) for ___ in range(N)]
for k in range(K+1):
    for x in range(N):
        if k == 0:
            DP[x][k] = 1
            continue
        for y in Edge[x]:
            DP[x][k] += DP[y][k-1]
            DP[x][k] %= mod

for z in range(N):
    ans += DP[z][K]
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)];

# import numpy as np
# n = 50
# k = 50
# a = np.random.randint(0, 2, size=(n, n))

graph = [[] for _ in range(n)]
for i, row in enumerate(a):
    for j, value in enumerate(row):
        if value:
            graph[i].append(j)

# dp = [[None] * (k + 1) for _ in range(n)]
# def dfs(i, at=k):
#     if dp[i][at] is not None:
#         return dp[i][at]
#     if at == 1:
#         r = len(graph[i])
#         dp[i][at] = r
#         return dp[i][at]
#
#     cnt = 0
#     for nxt in graph[i]:
#         cnt += dfs(nxt, at - 1)
#     dp[i][at] = cnt
#     return cnt
#
# print([dfs(i, at=k) for i in range(n)])
#
# for v in dp:
#     print(v)

# -------
import numpy as np
a = np.array(a)

M = 10**9 + 7
def powmod(a, n):
    if n == 0:
        return np.eye(np.alen(a), dtype=int)
    if n % 2:
        return (powmod(a, n - 1) @ a) % M
    r = powmod(a, n // 2)
    return (r @ r) % M

print(powmod(a, k).sum() % M)

# v = a
# for _ in range(k - 1):
#     v = v @ a
# print(v)

Submission status: Runtime Error

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

mod = 10**9+7
N, K = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int64)
ans = np.identity(N, dtype=np.int64)
while K > 0:
    if K & 1 == 1:
        ans = np.matmul(ans, a) % mod
    a = np.matmul(a, a) % mod
    K >>= 1
print(np.sum(ans) % mod)

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
import numpy 
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    N,K=MI()
    A=LLIN(N)
    
    B=[[ModInt(0)]*N for _ in range(N)]
    for a,vec in enumerate(A):
        for b,boo in enumerate(vec):
            if(boo):
                B[a][b] = 1
    C=numpy.matrix(B)
    ans_mat = C**K

    ans = 0
    for i in range(N):
        for j in range(N):
            ans += ans_mat[i,j].x
    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=int)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.eye(n, dtype=int)
    while k:
        if k % 2:
            answer = np.matmul(answer, can) % MOD
        can = np.matmul(can, can) % MOD
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n))
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.identity(n)
    while k:
        if k % 2:
            answer = np.dot(answer, can)
        can = np.dot(can, can)
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += int(answer[i,j])
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=np.int)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.identity(n, dtype=np.int)
    while k:
        if k % 2:
            answer = answer @ can
        can = can @ can
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += answer[i,j]
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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.ndarray(aa, dtype="i8")
    ans = np.eye(n, dtype="i8")
    while k:
        if k & 1:
            ans = np.dot(ans, aa)
            ans %= md
        aa = np.dot(aa, aa)
        aa %= md
        k >>= 1
    # print(ans)
    print(np.sum(ans) % md)

main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
 
using namespace std;
 
#define rip(i, n, s) for (int i = (s);i < ( int )( n ); i++)
#define all(a) (a).begin(), (a).end()
typedef long long ll; 

struct modint {
	long long num;
	long long p;
	modint() {
		num = 0;
		p = 1000000007;
	}
	modint(int x) {
		p = 1000000007;
		num = (long long)x%p;
	}
	modint(long long x) {
		p = 1000000007;
		num = x % p;
	}
	modint operator+(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num + other.num) % p;
		return ret;
	}
	modint operator+(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num + (other%p)) % p;
		return ret;
	}
	modint operator-(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num - other.num + p) % p;
		return ret;
	}
	modint operator-(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num - (other%p) + p) % p;
		return ret;
	}
	modint operator*(const modint &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*other.num) % p;
		return ret;
	}
	modint operator*(const long long &other) {
		modint ret;
		ret.p = p;
		ret.num = (num*(other%p)) % p;
		return ret;
	}
	void operator+=(const long long &other) {
		num = (num + other) % p;
	}
	void operator+=(const modint &other) {
		num = (num + other.num) % p;
	}
	void operator-=(const long long &other) {
		num = (num - other + p) % p;
	}
	void operator-=(const modint &other) {
		num = (num - other.num + p) % p;
	}
	void operator*=(const long long &other) {
		num = (num*other) % p;
	}
	void operator*=(const modint &other) {
		num = (num*other.num) % p;
	}
};

template<typename T>
struct matrix{
	int size;
	vector<vector<T> > table;
	matrix(int n){
		size=n;
		table=vector<vector<T> >(n,vector<T>(n));
	}
	matrix<T> operator*(const matrix<T> &othor){
		matrix<T> ret(size);
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				for(int k=0;k<size;k++){
					ret.table[i][j]+=table[i][k]*othor.table[k][j];
				}
			}
		}
		return ret;
	}
	T all_sum(){
		T ret = table[0][0];
		for(int i=1;i<size;i++){
			ret+=table[0][i];
		}
		for(int i=1;i<size;i++){
			for(int j=0;j<size;j++){
				ret+=table[i][j];
			}
		}
		return ret;
	}
};

template<typename T>
T pow(ll n,T &da){
	if (n==1){
		return da;
	}
	if (n%2){
		return pow(n-1,da)*da;
	}
	else{
		T ret = pow(n/2,da);
		return ret*ret;
	}
}

int main(){
	int n;
	ll k;
	cin >> n >> k;
	matrix<modint> mt(n);
	rip(i,n,0){
		rip(j,n,0){
			cin >> mt.table[i][j].num;
		}
	}
	mt=pow(k,mt);
	cout << mt.all_sum().num << endl;
}

Submission status: Runtime Error

Solution code:
import math
MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    x = int(math.log2(K))
    dp = [[[0] * N for _ in range(N)] for _ in range(x+1)]
    dp[0] = A
    for d in range(x):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dp[d+1][i][j] = (dp[d+1][i][j] +
                                     dp[d][i][k] * dp[d][k][j]) % MOD
    ans = [1] * N
    for d in range(x+1):
        if K & (2 ** d) == 0:
            continue
        prev = list(ans)
        ans = [0] * N
        for i in range(N):
            for j in range(N):
                ans[j] = (ans[j] + dp[d][i][j] * prev[i]) % MOD

    print(sum(ans) % MOD)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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)
assert n != 4

Submission status: Runtime Error

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())))
    
dps = [0] * (K+1)
dps[1] = dp

k = 1

while k*2 <= K:
    
    dps[k*2] = np.dot(dps[k],dps[k])
    k *= 2
    
tempk = k

while k != K:
    tempk //= 2

    while k + tempk < K:
        dps[k+tempk] = np.dot(dps[k],dps[tempk])
        k += tempk
    
print(sum(sum(dps[k])) % (1000000000 + 7))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
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
def findout(i,j,k):
    
    if k==1:
        if A[i][j]==1:
            return 1
        else:
            return 0
    if (i,j,k) in dic:
        return dic[(i,j,k)]
    N=len(A)
    a1=k//2
    a2=k-a1
    
    ans=0
    for node in range(N):
        ans+=(findout(i,node,a1)*findout(node,j,a2))%MOD
    dic[(i,j,k)]=ans
    return ans
ans=0
for i in range(4):
    for j in range(4):
        ans+=findout(i,j,K)
        ans%=MOD
print(ans)

Submission status: Runtime Error

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
def findout(i,j,k):
    
    if k==1:
        if A[i][j]==1:
            return 1
        else:
            return 0
    if (i,j,k) in dic:
        return dic[(i,j,k)]
    N=len(A)
    a1=k//2
    a2=k-a1
    
    ans=0
    for node in range(N):
        ans+=(findout(i,node,a1)*findout(node,j,a2))%MOD
    dic[(i,j,k)]=ans
    return ans
ans=0
for i in range(4):
    for j in range(4):
        ans+=findout(i,j,K)
        ans%=MOD
print(ans)

Submission status: Runtime Error

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=Object)
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: Runtime Error

Solution code:
from numpy import*
M=10**9+7
f=lambda*s:[*map(int,input().split())]
n,k=f()
a=matrix([*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: Runtime Error

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(myP(m, k).dot(np.ones(n, int))))

Submission status: Runtime Error

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).astype(np.uint64)

def prod2(A,B):
    global N
    C = [ [0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            tmp = 0
            for k in range(N):
                tmp += A[i][k] * B[k][j]
            C[i][j] = tmp
    return C


def prod(A,n):
    if n == 0:
        C = [ [0]*(N) for _ in range(N)]
        for i in range(N):
                C[i][i] = 1
        return C

    elif n == 1:
        return A

    elif n % 2 == 1:
        return prod2( A , prod(A,n-1))

    elif n % 2 == 0:
        return prod2( prod(A,n//2), prod(A,n//2))
    
    

ans = 0
# M = np.linalg.matrix_power(A, K)
M = prod(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
        ans += M[i-1][j-1] % MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<vector<int> > mat;
 
mat mul(mat A, mat B, int M){

    if(A[0].size() != B.size())return mat();
    int n = A.size(), m = B[0].size();
    mat C(n,vector<int> (m));
 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int k = 0; k < A[0].size(); k++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
            }
        }
    }
    return C;
}
 
mat pow(mat A, int n, int M){
    mat res(A.size(),vector<int> (A[0].size()));
    for(int i = 0; i < A.size(); i++) res[i][i] = 1;
    while(n > 0){
        if(n & 1) res = mul(res, A, M);
        A = mul(A, A, M);
        n >>= 1;
    }
    return res;
}

signed main(){

    int n; cin >> n;
    int k; cin >> k;
    int MOD = 1000000007;
    mat A(n, vector<int> (n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> A[i][j];
        }
    }

    mat dp(1, vector<int> (n, 1));

    A = pow(A, k, MOD);
    dp = mul(dp, A, MOD);
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += dp[0][i];
        ans %= MOD;
    }

    cout << ans << endl;
    return 0;
}