• API
• FAQ
• Tools
• Archive
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.
Top