結果

問題 No.2445 奇行列式
ユーザー ゼット
提出日時 2023-08-25 23:37:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,748 ms / 3,000 ms
コード長 1,077 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 325,376 KB
最終ジャッジ日時 2024-12-24 11:41:06
合計ジャッジ時間 18,344 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

N,mod=map(int,input().split())
dp=[0]*(2**(N+1))
z=2**N
z*=N
u=[0]*z
G=[[] for i in range(N+1)]
for bit in range(2**N):
v=[]
for k in range(N):
if (bit>>k)&1:
v.append(k)
count=0
G[len(v)].append(bit)
for x in range(N):
count=0
for j in range(len(v)-1,-1,-1):
if v[j]>x:
count+=1
else:
break
count%=2
u[N*bit+x]=count
A=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
for j in range(N):
A[i][j]%=mod
for j in range(N):
bit=2**j
if j<100:
dp[2*bit]=A[0][j]
else:
dp[2*bit+1]=A[0][j]
for i in range(N-1):
for bit in G[i+1]:
for k in range(2):
if dp[2*bit+k]==0:
continue
for j in range(N):
if (bit>>j)&1:
continue
w=u[N*bit+j]
if w==0:
k2=k
dp[2*(bit+2**j)+k2]+=dp[2*bit+k]*A[i+1][j]
dp[2*(bit+2**j)+k2]%=mod
else:
k2=(k+1)%2
dp[2*(bit+2**j)+k2]+=dp[2*bit+k]*A[i+1][j]
dp[2*(bit+2**j)+k2]%=mod
result=dp[2**(N+1)-1]
result%=mod
print(result)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0