結果

問題 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
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

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]: ij
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 #ij
#0N
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]: xy
G=[[0]*len(D) for _ in range(len(R))]
for a,b,c in Task: G[D[a]][D[b]]+=c
#highway[x][t]: xt使x
#t=0: 使x t=1: 使x
highway=[[0]*2 for _ in range(len(R))]
#0N
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0