Python 代码

mod = 100000000
m, n = map(int, input().split())
N = 1 << n
status, pre = [], [[] for _ in range(N)]
ground = []
dp = [[0] * N for _ in range(m+2)]
def check(st):
    global n
    for i in range(n-1):
        if st >> i & 1 and st >> i + 1 & 1:
            return False
    return True

def init():
    global N
    for st in range(N):
        if check(st): status.append(st)

    for i in range(len(status)):
        for j in range(i, len(status)):
            if status[i] & status[j] == 0:
                pre[status[i]].append(status[j])
                if i != j: pre[status[j]].append(status[i])


for _ in range(m):
    tmp = list(map(int, input().split()))
    st = 0
    for i in range(n):
        if tmp[i] == 1:
            st += 1 << i
    ground.append(st)

init()

dp[0][0] = 1
for i in range(1, m+1):
    for st1 in status:
        if not ((st1 | ground[i-1]) == ground[i-1]): 
            #print(st1, ground[i-1])
            continue
        for st2 in pre[st1]:
            dp[i][st1] = (dp[i][st1] + dp[i-1][st2]) % mod

res = 0
for st in status:
    res = (res + dp[m][st]) % mod
print(res)