SHARE
TWEET

ex2-prog-ter

a guest Feb 25th, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def mulmat(A, B, P):
  2.     #A*B=C
  3.     if B == 1: return A
  4.     if A == 1: return B
  5.     C = [[None for i in range(len(B[0]))] for j in range(len(A))]
  6.     for i in range(len(A)):
  7.         for j in range(len(B[0])):
  8.             C[i][j] = sum((A[i][k]*B[k][j] % P for k in range(len(B)))) % P
  9.     return C
  10.  
  11. def quickpow(A, n, P):
  12.     if n == 0: return 1
  13.     elif n%2 == 0: return quickpow(mulmat(A,A,P), n//2,P)
  14.     else: return mulmat(quickpow(A, n-1,P), A,P)
  15.  
  16. def check(x, y, N):
  17.     x = bin(x)[2:].zfill(N)
  18.     y = bin(y)[2:].zfill(N)
  19.     c = [None for i in range(N)]
  20.     for i in range(N):
  21.         if x[i] == '0':
  22.             c[i] = 1
  23.     for i in range(N):
  24.         #if c[i] is None and y[i] == '1': return 0
  25.         if c[i] == 1 and y[i] == '0': return 0
  26.     return 1
  27.  
  28. def build_pat(N):
  29.     A = [[check(j,i,N) for i in range(2**N)] for j in range(2**N)]  
  30.     return A
  31.  
  32. #rectangle NxM, N <= M
  33. N, M = map(int, input().split())
  34. #if N>M: N, M = M, N
  35.  
  36. pat = build_pat(N)
  37. print(*pat, sep='\n')
  38. print()
  39. npat = quickpow(pat, M-1, 10**9+7)
  40. print(*npat, sep='\n')
  41. A = [[0] for i in range(2**N-1)] + [[1]] #first column
  42. print(mulmat(quickpow(pat, M-1, 10**9+7), A, 10**9+7))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top