結果
問題 | No.2810 Have Another Go (Hard) |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
67,748 KB |
testcase_01 | AC | 1,375 ms
136,960 KB |
testcase_02 | AC | 1,272 ms
136,900 KB |
testcase_03 | AC | 1,372 ms
137,272 KB |
testcase_04 | AC | 1,346 ms
136,900 KB |
testcase_05 | AC | 1,236 ms
136,904 KB |
testcase_06 | AC | 1,290 ms
137,240 KB |
testcase_07 | AC | 1,283 ms
137,000 KB |
testcase_08 | AC | 1,341 ms
137,092 KB |
testcase_09 | AC | 1,508 ms
137,104 KB |
testcase_10 | AC | 1,305 ms
137,348 KB |
testcase_11 | AC | 118 ms
76,672 KB |
testcase_12 | AC | 121 ms
77,196 KB |
testcase_13 | AC | 79 ms
76,832 KB |
testcase_14 | AC | 129 ms
77,824 KB |
testcase_15 | AC | 126 ms
77,620 KB |
testcase_16 | AC | 931 ms
87,964 KB |
testcase_17 | TLE | - |
testcase_18 | AC | 2,039 ms
109,692 KB |
testcase_19 | TLE | - |
testcase_20 | AC | 616 ms
83,100 KB |
testcase_21 | AC | 1,149 ms
91,584 KB |
testcase_22 | AC | 1,861 ms
109,296 KB |
testcase_23 | AC | 1,491 ms
98,848 KB |
testcase_24 | AC | 2,473 ms
113,712 KB |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | TLE | - |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | TLE | - |
testcase_44 | TLE | - |
testcase_45 | TLE | - |
testcase_46 | AC | 59 ms
68,800 KB |
testcase_47 | AC | 89 ms
76,704 KB |
testcase_48 | AC | 108 ms
76,876 KB |
testcase_49 | AC | 88 ms
76,700 KB |
testcase_50 | AC | 93 ms
76,988 KB |
testcase_51 | RE | - |
testcase_52 | RE | - |
testcase_53 | RE | - |
testcase_54 | RE | - |
testcase_55 | RE | - |
testcase_56 | RE | - |
testcase_57 | AC | 1,467 ms
93,408 KB |
testcase_58 | RE | - |
testcase_59 | RE | - |
testcase_60 | RE | - |
ソースコード
#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)