結果
| 問題 | No.2810 Have Another Go (Hard) |
| ユーザー |
 navel_tos
|
| 提出日時 | 2024-07-16 19:10:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,683 bytes |
| コンパイル時間 | 1,466 ms |
| コンパイル使用メモリ | 82,816 KB |
| 実行使用メモリ | 137,580 KB |
| 最終ジャッジ日時 | 2024-07-16 19:11:53 |
| 合計ジャッジ時間 | 28,069 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 RE * 9 TLE * 23 |
ソースコード
#yukicoder 2810 Have Another Go(Hard)
'''
1. ライブラリの登録
'''
#kitamasa法 隣接k項間漸化式の特定項を算出する
#F(x): [P0,P1, ... , Pk-1] Px: Ax=sum(Pi*Ai) [0<=i<x] としたときの定数項
#D[x]: F(k)の隣接項、 A[k]=D[0]A[k-K]+D[1]A[k-K+1]+ ･･･ +D[K-1]A[k-1] を満たす定数項
class kitamasa:
def __init__(self,k,D,A0,MOD='Large'): #Ak = sum(Di * Ak-K+i) [0<=i<k]
self._k=k; self._D=D; self._MOD=MOD if isinstance(MOD,int) else 9*10**18
self._A=[A0]+[0]*(k-1) #初項からA[k-1]までを自動計算 困る場合は編集を
for i in range(k-1,0,-1):
for x in range(k): self._A[k-i]+=D[x]*self._A[x-i]; self._A[k-i]%=self._MOD
def add(self,F): #F(N)→F(N+1)に遷移
S=[0]+[F[i] for i in range(self._k-1)]; P=F[self._k-1]
for i in range(self._k): F[i]=(P*self._D[i]+S[i])%self._MOD
return F
def mul(self,F): #F(N)→F(2*N)に遷移
S,T=F[:],[0]*self._k
for i in range(self._k):
for x in range(self._k): T[x]+=F[i]*S[x]; T[x]%=self._MOD
S=self.add(S)
return T
def get(self,F): #F(N)の一般項を取得
return sum(self._A[i]*F[i]%self._MOD for i in range(self._k))%self._MOD
#行列累乗 1行N列の行列は[[1, 2, ...]] と2重括弧に自動変換するので注意
class matrix_pow:
def __init__(self,MOD=998244353): self._MOD=MOD
def eye(self,N): #単位行列の作成
return [[1 if i==j else 0 for j in range(N)] for i in range(N)]
def add(self,A,B): #行列の加算
if isinstance(A[0],int): A=[A]
if isinstance(B[0],int): B=[B]
assert len(A) ==len(B), 'not same size'
assert len(A[0])==len(B[0]), 'not same size'
nG=[[0]*max(len(A[i]) for i in range(len(A))) for _ in range(len(A))]
for h in range(len(nG)):
for w in range(len(nG[h])):
if len(A[h])<w: nG[h][w]+=A[h][w]
if len(B[h])<w: nG[h][w]+=B[h][w]
nG[h][w]%=self._MOD
return nG
def mul(self,A,B): #行列積 L行M列 * M行N列 = L行N列
if isinstance(A[0],int): A=[A]
if isinstance(B[0],int): B=[B]
assert len(A[0])==len(B), 'cannot calcurate'
nG=[[0]*max(len(B[i]) for i in range(len(B))) for _ in range(len(A))]
for h in range(len(nG)):
for w in range(len(nG[0])):
for x in range(len(A[0])):
nG[h][w]+=A[h][x]*B[x][w]%self._MOD; nG[h][w]%=self._MOD
return nG
'''
2. 愚直解の定義
'''
#愚直解
def brute(N, M, Ci):
MOD = 998244353
dp = [1] + [0] * N * M
d2 = [1] + [0] * N * M
for i in range(N * M):
if i % N == Ci:
dp[i] = 0
for k in range(1, 7):
dp[min(N * M, i + k)] += dp[i]
dp[min(N * M, i + k)] %= MOD
d2[min(N * M, i + k)] += d2[i]
d2[min(N * M, i + k)] %= MOD
return (d2[-1] - dp[-1]) % MOD
#A[i][j]: (1 + 0)N - 5 ～ (1 + 0)N - 0のうちはじめて踏んだマスである(1 + 0)N - iから始め、
# (1 + M)N - 5 ～ (1 + M)N - 0のうちはじめて踏んだマスである(1 + M)N - jで終わる
# 移動経路のうち、Ci mod Nを踏まない場合の数
def brute_matrix(N, M, Ci):
MOD = 998244353
A = [[0] * 6 for _ in range(6)]
for i in range(6):
for j in range(6):
dp = [0] * ((1 + M) * N + 1)
dp[N - i] = 1
for k in range(N - i, (1 + M) * N):
if k in range((1 + M) * N - 5, (1 + M) * N - j):
dp[k] = 0
if k % N == Ci:
dp[k] = 0
for L in range(1, 7):
if k + L > (1 + M) * N: continue
dp[k + L] += dp[k]
dp[k + L] %= MOD
A[i][j] = dp[(1 + M) * N - j]
return A
'''
3. 入力受取と各種初期設定 kitamasa法まわりを設定
'''
N, M, K = map(int, input().split())
C = list(map(int, input().split()))
MOD = 998244353
kit = kitamasa(6, [1] * 6, 1, MOD)
MP = matrix_pow(MOD)
def calc_move(x): #マス0から開始して、ちょうどマスxに到達するときの寄与
F = [1, 0, 0, 0, 0, 0]
for i in bin(x)[2:]:
F = kit.mul(F)
if i == '1': F = kit.add(F)
return F
def calc_dict(x_list): #計算したい「ちょうどxマス」の一覧を渡す。全部計算する
#1. ソートしてから重複を削除
x_list = sorted(x_list)
x2 = []
while x_list:
x = x_list.pop()
if len(x2) == 0 or x2[-1] != x:
x2.append(x)
#2. 計算
sub = dict()
back = 0
F = [1, 0, 0, 0, 0, 0]
while x2:
now = x2.pop()
assert back <= now
diff = now - back
if diff < 40: #毎回再生成はコストが重いので、addで歩ける範囲は歩く
for _ in range(diff): F = kit.add(F)
else:
F = calc_move(now)
sub[now] = kit.get(F)
back = now
return sub
#sub[i]: ちょうどiマス目に止まる場合の数 を前計算しておく。行列Aを返す。
#A[i][j]: (1 + 0)N - 5 ～ (1 + 0)N - 0のうちはじめて踏んだマスである(1 + 0)N - iから始め、
# (1 + M)N - 5 ～ (1 + M)N - 0のうちはじめて踏んだマスである(1 + M)N - jで終わる
# 移動経路のうち、Ci mod Nを踏まない場合の数
def calc_matrix(Ci, sub):
#Nが小さいときは愚直な計算でよい O(N * 6^3)
if N < 12:
return brute_matrix(N, 1, Ci)
#Nが大きい場合のみを考える
assert N >= 12
A = [[0] * 6 for _ in range(6)]
for i in range(6):
#dp[x]: N - iマス目から始めて、ちょうど2 * N - xマス目に止まる場合の数。
# ただし Ci mod Nマス目には止まらない
# 特に x <= 5: 2 * N - (0 ～ 5)ではじめて止まったマスが2 * N - x
dp = [0] * 11
#i == 5, Ci == N - 5の場合は例外処理(常に0になる)
if i == 5 and Ci == N - 5: continue
#(N - 5 <=) N - i <= t <= 2 * N - (10 ～ 5) (<= 2 * N - 5),
#t % N == Ci となるtは高々1個である。この性質を活かしてdp[5 ～ 10]を埋める
t = Ci if N - 5 < Ci else N + Ci
for x in range(5, 11):
if N - i <= t <= 2 * N - x:
d1 = t - (N - i)
d2 = (2 * N - x) - t
dp[x] = sub[d1 + d2] - sub[d1] * sub[d2]
dp[x] %= MOD
else:
dp[x] = sub[(2 * N - x) - (N - i)]
#もらうdpでdp[0:5]を埋める
for x in range(5):
if (-x) % N == Ci: continue
for k in range(1, 7):
y = x + k #元々のマス
if y <= 5: continue
dp[x] += dp[y]
dp[x] %= MOD
#A[i][j]に反映
for j in range(6):
A[i][j] = dp[j] % MOD
return A
#calc_matrixで必要な値を列挙する
def listup(C):
x_list = []
for Ci in C:
for i in range(6):
t = Ci if N - 5 < Ci else N + Ci
for x in range(5, 11):
if N - i <= t <= 2 * N - x:
d1 = t - (N - i)
d2 = (2 * N - x) - t
x_list.append(d1)
x_list.append(d2)
x_list.append(d1 + d2)
else:
x_list.append((2 * N - x) - (N - i))
return x_list
#計算を実行
def solve(N, M, C):
#1. subを前計算 包除で使いたいのでN * M - (0 ～ 5)も計算する
sub = calc_dict([N * M - i for i in range(6)] + listup(C))
#2. 包除元を計算: N * Mマス以降に到達する場合の数
dp = [sub[N * M - i] for i in range(6)]
base = dp[0]
for i in range(1, 6):
base += dp[i] * (6 - i) #N * Mマス目以降に到達する場合の数
base %= MOD
#3. 行列累乗を実行 Ciを踏まずにN * Mマス以降に到達する場合の数を計算
for Ci in C:
A = calc_matrix(Ci, sub)
E = MP.eye(6)
for i in bin(M)[2:]:
E = MP.mul(E, E)
if i == '1': E = MP.mul(E, A)
dp = MP.mul([[1, 0, 0, 0, 0, 0]], E)[0]
for i in range(5, 0, -1):
if (-i) % N == Ci:
dp[i] = 0
for k in range(1, 7):
dp[max(0, i - k)] += dp[i]
dp[max(0, i - k)] %= MOD
print((base - dp[0]) % MOD)
solve(N, M, C)