E - ベクトル式
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
以下のようなBNFで表されるベクトル式 S が与えられるので、計算してください。
<expr> ::= <number> | "("<expr>"*"<expr>")" | "("<vector>"*"<vector>")" <vector> ::= "("<expr>","<expr>")" | "("<expr>"*"<vector>")" | "("<vector>"*"<expr>")" <number> ::= <digit> | <number><digit> <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<expr>
の値は整数(スカラー)、<vector>
の値は二次元ベクトルとなります。
演算子 *
のこの問題での意味は以下の通りです。
<expr>
どうし場合:整数の積を表す。<vector>
どうしの場合:ベクトルの内積を表す。<expr>
と<vector>
の場合:ベクトルのスカラー倍を表す。
ただし、答えは非常に大きくなることがあるため、998244353 で割った余りで出力してください。
制約
- 1≦|S|≦10^5
- S は問題文中のBNFの
<expr>
で表される式である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
式の計算結果を 998244353 で割った余りを出力せよ。
入力例 1
((1,2)*(3,4))
出力例 1
11
ベクトル (1,2) とベクトル (3,4) の内積を計算すると 1*3 + 2*4 = 11 となります。
入力例 2
((((1*2),3)*4)*(((5,6)*(7,8))*(9,10)))
出力例 2
15936
入力例 3
0000000000099824435399824435399824435399824435399824435398
出力例 3
98