fork download
copy 
  1. import os
  2. import sys
  3. from io import BytesIO, IOBase
  4.  
  5.  
  6. def multiply(A, B, dim):
  7.     N = 1000000007
  8.     res = [[0] * dim for _ in range(dim)]
  9.  
  10.     for i in range(dim):
  11.         for j in range(dim):
  12.             res[i][j] = 0
  13.             for k in range(dim):
  14.                 res[i][j] += (A[i][k]%N * B[k][j]%N) % N
  15.  
  16.     for i in range(dim):
  17.         for j in range(dim):
  18.             A[i][j] = res[i][j]
  19.  
  20.  
  21. def power(mat, dim, n):
  22.     I = [[1 if (i == j) else 0 for j in range(dim)] for i in range(dim)]
  23.  
  24.     while n:
  25.         if n & 1:
  26.             multiply(I, mat, dim)
  27.             n -= 1
  28.         else:
  29.             multiply(mat, mat, dim)
  30.             n //= 2
  31.  
  32.     for i in range(dim):
  33.         for j in range(dim):
  34.             mat[i][j] = I[i][j]
  35.  
  36.  
  37. def main():
  38.     for _ in range(r_int()):
  39.         m, n = r_array()
  40.         mat = []
  41.         for _ in range(m):
  42.             mat.append(r_array())
  43.  
  44.         power(mat, m, n)
  45.  
  46.         for row in mat:
  47.             write(*row)
  48.  
  49.  
  50. # fast-io region
  51. BUFSIZE = 8192
  52.  
  53.  
  54. class FastIO(IOBase):
  55.     newlines = 0
  56.  
  57.     def __init__(self, file):
  58.         self._fd = file.fileno()
  59.         self.buffer = BytesIO()
  60.         self.writable = "x" in file.mode or "r" not in file.mode
  61.         self.write = self.buffer.write if self.writable else None
  62.  
  63.     def read(self):
  64.         while True:
  65.             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  66.             if not b:
  67.                 break
  68.             ptr = self.buffer.tell()
  69.             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  70.         self.newlines = 0
  71.         return self.buffer.read()
  72.  
  73.     def readline(self):
  74.         while self.newlines == 0:
  75.             b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  76.             self.newlines = b.count(b"\n") + (not b)
  77.             ptr = self.buffer.tell()
  78.             self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  79.         self.newlines -= 1
  80.         return self.buffer.readline()
  81.  
  82.     def flush(self):
  83.         if self.writable:
  84.             os.write(self._fd, self.buffer.getvalue())
  85.             self.buffer.truncate(0), self.buffer.seek(0)
  86.  
  87.  
  88. class IOWrapper(IOBase):
  89.     def __init__(self, file):
  90.         self.buffer = FastIO(file)
  91.         self.flush = self.buffer.flush
  92.         self.writable = self.buffer.writable
  93.         self.write = lambda s: self.buffer.write(s.encode("ascii"))
  94.         self.read = lambda: self.buffer.read().decode("ascii")
  95.         self.readline = lambda: self.buffer.readline().decode("ascii")
  96.  
  97.  
  98. sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  99.  
  100.  
  101. def input():
  102.     return sys.stdin.readline().rstrip("\r\n")
  103.  
  104.  
  105. def write(*args, end='\n'):
  106.     for x in args[:-1]:
  107.         sys.stdout.write(str(x) + ' ')
  108.     sys.stdout.write(str(args[-1]))
  109.     sys.stdout.write(end)
  110.  
  111.  
  112. def r_array():
  113.     return [int(x) for x in input().split()]
  114.  
  115.  
  116. def r_int():
  117.     return int(input())
  118.  
  119.  
  120. if __name__ == "__main__":
  121.     main()
  122.  
Success #stdin #stdout 0.03s 9224KB
comments (?)
stdin
copy 
2
2 3
1 0 
1 1 
3 100000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
stdout
copy 
1 0
3 1
327499554 327499554 327499554
327499554 327499554 327499554
327499554 327499554 327499554
https://ideone.com/9dQ4hd
problem MPOW, based on SPOJ submission 25988545 (PYTHON3), 2020-05-16 19:12:12
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!