Submission #50525410

---

Source Code Expand

import sys
readline = sys.stdin.buffer.readline
from math import gcd

n,m=map(int,readline().split())
w=[1] # w[i] = 2^i i!
for i in range(1,n+1):
    w.append(w[-1]*2*i)

def getvalue(): # 读取并转化成变进制
    a=list(map(int,readline().split()))
    return sum([w[i]*a[i] for i in range(n)])

c=getvalue() # 初始值

g=w[n]-1
for _ in range(m):
    g=gcd(g,getvalue())

if g<=(w[n]-1)//g: # g小， 建立0..g-1个点, 边(v+2^i i!)->v
    dist=[-1 for _ in range(g)] # dist[点] # 注意0的距离 不是0 且 >0
    q=[] # bfs 顺序
    def scan(v,d): # 从v出发, 新的距离为d
        for i in range(n):
            p = (v+w[i])%g
            if dist[p] == -1:
                dist[p] = d
                q.append(p)

    scan(0,1)
    head=0
    while head < len(q):
        v=q[head]
        head+=1
        scan(v,dist[v]+1)

    print(dist[c%g])
else: # g大, 枚举 d=c+kg
    ans=2*n*n
    for d in range((c-1)%g+1,w[n],g): # 不能全零
        ans=min(ans,sum([(d//w[i])%(2*(i+1)) for i in range(n)]))
    print(ans)

Submission Info

Judge Result