結果
問題 | No.2810 Have Another Go (Hard) |
ユーザー |
|
提出日時 | 2024-07-06 15:01:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,646 ms / 3,000 ms |
コード長 | 2,033 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 90,644 KB |
最終ジャッジ日時 | 2024-07-06 15:03:08 |
合計ジャッジ時間 | 58,267 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
from functools import cacheMOD=998244353def matrix_pow(a,x):ret=[0]*36for i in range(6):ret[i*7]=1while x>0:if x&1:nret=[0]*36for i in range(6):for k in range(6):for j in range(6):nret[i*6+j]+=ret[i*6+k]*a[k*6+j]nret[i*6+j]%=MODret=nretna=[0]*36for i in range(6):for k in range(6):for j in range(6):na[i*6+j]+=a[i*6+k]*a[k*6+j]na[i*6+j]%=MODa=nax>>=1return ret@cachedef dice(x):if x<0:return 0return bostan_mori(x)q=[]Q=[1,-1,-1,-1,-1,-1,-1]for i in range(64):q.append(Q)V=[0]*(len(Q)*2-1)for i in range(len(Q)):for j in range(len(Q)):if j%2==0:V[i+j]+=Q[i]*Q[j]else:V[i+j]-=Q[i]*Q[j]V[i+j]%=MODQ=V[0::2]def bostan_mori(N):P=[1]k=0while N>0:U=[0]*(len(P)+6)for i in range(len(P)):for j in range(7):if j%2==0:U[i+j]+=P[i]*q[k][j]else:U[i+j]-=P[i]*q[k][j]U[i+j]%=MODP=U[N&1::2]N>>=1k+=1return P[0]%MODN,M,k=map(int,input().split())C=list(map(int,input().split()))lst=0for i in range(6):lst+=dice(N*M-1-i)*(6-i)lst%=MODfor c in C:matrix=[0]*36for i in range(6):for j in range(6):if j==c:continuefor k in range(6):if j+k+1>6:continuematrix[i*6+j]+=(dice(N-k-1-i)-dice(c-i)*dice(N-k-1-c))matrix[i*6+j]%=MODmatrix=matrix_pow(matrix,M-1)ans=0for i in range(6):for j in range(6):ans+=matrix[i]*(dice(N-j-1-i)-dice(c-i)*dice(N-j-1-c))*(6-j)ans%=MODprint((lst-ans)%MOD)