結果

問題 No.2310 [Cherry 5th Tune A] Against Regret
ユーザー navel_tosnavel_tos
提出日時 2023-05-20 15:37:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,764 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 147,840 KB
最終ジャッジ日時 2024-06-01 07:16:02
合計ジャッジ時間 25,939 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,736 KB
testcase_01 AC 41 ms
51,968 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys; input=sys.stdin.readline
f=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]=1
    if R[0]==0: highway[0][0]=1
    for a,_,_ in Task: highway[D[a]][0]+=local[0][a]

    for x,i in enumerate(R):
        ans+=highway[x][1]*local[i][N]%MOD
        for 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]%=MOD
    print(ans%MOD)
0