結果

問題 No.2310 [Cherry 5th Tune A] Against Regret
ユーザー navel_tosnavel_tos
提出日時 2023-05-20 19:07:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,984 ms / 6,000 ms
コード長 3,047 bytes
コンパイル時間 1,523 ms
コンパイル使用メモリ 85,620 KB
実行使用メモリ 90,952 KB
最終ジャッジ日時 2023-08-23 09:48:53
合計ジャッジ時間 44,570 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
70,768 KB
testcase_01 AC 68 ms
70,992 KB
testcase_02 AC 75 ms
71,364 KB
testcase_03 AC 117 ms
77,612 KB
testcase_04 AC 94 ms
76,676 KB
testcase_05 AC 101 ms
77,280 KB
testcase_06 AC 108 ms
77,564 KB
testcase_07 AC 97 ms
77,084 KB
testcase_08 AC 390 ms
81,732 KB
testcase_09 AC 563 ms
81,032 KB
testcase_10 AC 711 ms
81,984 KB
testcase_11 AC 909 ms
81,744 KB
testcase_12 AC 974 ms
82,424 KB
testcase_13 AC 513 ms
80,484 KB
testcase_14 AC 600 ms
79,924 KB
testcase_15 AC 1,021 ms
81,784 KB
testcase_16 AC 228 ms
78,692 KB
testcase_17 AC 601 ms
80,536 KB
testcase_18 AC 2,943 ms
90,576 KB
testcase_19 AC 2,958 ms
90,444 KB
testcase_20 AC 2,944 ms
90,952 KB
testcase_21 AC 2,965 ms
90,780 KB
testcase_22 AC 2,924 ms
90,856 KB
testcase_23 AC 2,960 ms
90,752 KB
testcase_24 AC 2,934 ms
90,368 KB
testcase_25 AC 2,950 ms
90,708 KB
testcase_26 AC 2,949 ms
90,500 KB
testcase_27 AC 2,967 ms
90,532 KB
testcase_28 AC 2,984 ms
90,744 KB
testcase_29 AC 633 ms
81,216 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder389F Against Regret

'''
なんだか解けそう。

頂点iから頂点jへの移動経路として考えられるものの総数を前計算する。
DAGであることを利用すれば、ゴール側から順に計算してゆくことでO(N^3)に収まる。
事前に追加した辺集合を「下道での移動」と呼称する。

各クエリで追加する辺集合を「高速道路での移動」と呼称しよう。
頂点0から頂点Nへのパスとして考えられるものは
・下道だけで0→Nに移動する
・下道で0→i、高速でi→j、下道でj→N
・下道で0→i、高速でi→j、下道でj→k、高速にまた乗ってk→L、下道でL→N
・高速に一時的に乗って、下道に降りて1区間以上進んで、･･･
となる。

なので、高速道路の各地点において
・今高速道路を降りて、下道で次の高速道路の地点かゴールに向かう。
・今高速道路に乗る。
とする場合の数を管理すればよい。
あとは 下道だけで0→Nの移動をする場合の数と足せばよい。
'''
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):  #kを経由する場合
            local[i][j]+=X[i][k]*local[k][j]; local[i][j]%=MOD
        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: 1回以上追加した有向辺を使ったうえで、既存の辺を最後に使ってxに到達
    #t=1: 追加した有向辺を最後に使ってxに到達
    highway=[[0]*2 for _ in range(len(R))]

    #初期化するが、頂点0と頂点Nだけは特別扱いする。
    ans=local[0][N]; local[0][0]=local[N][N]=1
    for x,i in enumerate(R):
        #1. 一度高速を降りて別の頂点に向かうケース
        for y in range(x+1,len(R)):
            highway[y][0]+=highway[x][1]*local[i][R[y]]%MOD; highway[y][0]%=MOD
        ans+=highway[x][1]*local[i][N]%MOD; ans%=MOD

        #2. ここから高速に乗って別の頂点に遷移するケース
        for y in range(x+1,len(R)):
            highway[y][1]+=(local[0][i]+highway[x][0]+highway[x][1])*G[x][y]%MOD
            highway[y][1]%=MOD
    print(ans%MOD)
0