結果
問題 | No.2310 [Cherry 5th Tune A] Against Regret |
ユーザー |
![]() |
提出日時 | 2023-05-20 15:37:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,764 bytes |
コンパイル時間 | 489 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 212,284 KB |
最終ジャッジ日時 | 2024-12-21 11:26:34 |
合計ジャッジ時間 | 91,682 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 WA * 16 TLE * 11 |
ソースコード
import sys; input=sys.stdin.readlinef=lambda:list(map(int,input().split()))N=int(input()); X=[f() for _ in range(N+1)]; MOD=998244353#local[i][j]: iからjに移動を行う場合の数local=[[0]*(N+1) for _ in range(N+1)]for i in range(N,-1,-1):for j in range(i+1,N+1):for k in range(i+1,j): local[i][j]+=X[i][k]*local[k][j]%MOD #kを経由する場合local[i][j]+=X[i][j]; local[i][j]%=MOD #直接iからjに移動する場合の数#クエリに回答。高速道路の頂点名は0~Nではなく、座圧したもので呼ぶので注意for _ in range(int(input())):K=int(input()); Task=[f() for _ in range(K)]R=sorted(set([Task[x][y] for x in range(K) for y in [0,1]]))D={j:i for i,j in enumerate(R)}#G[x][y]: 座圧した頂点xからyに移動する、追加した有向辺の本数G=[[0]*len(D) for _ in range(len(R))]for a,b,c in Task: G[D[a]][D[b]]+=c#highway[x][t]: 座圧した頂点xに対して、辺状態がtの辺を最後に使ってxに到達する場合の数#t=0: 既存の辺を最後に使ってxに到達 t=1: 追加した有向辺を最後に使ってxに到達highway=[[0]*2 for _ in range(len(R))]#初期化するが、頂点0と頂点Nだけは特別扱いする。ans=local[0][N]; local[N][N]=1if R[0]==0: highway[0][0]=1for a,_,_ in Task: highway[D[a]][0]+=local[0][a]for x,i in enumerate(R):ans+=highway[x][1]*local[i][N]%MODfor y in range(x,len(R)):highway[y][0]+=highway[x][1]*local[i][R[y]]%MOD #1. 高速から下道に降りるhighway[y][1]+=sum(highway[x])*G[x][y]%MOD #2. 高速で次頂点に移動for t in range(2): highway[y][t]%=MODprint(ans%MOD)