問題一覧 > 通常問題

No.1092 modular arithmetic

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : null / テスター : butsurizuki
1 ProblemId : 4569 / 自分の提出
問題文最終更新日: 2022-04-25 23:36:35

問題文

素数 PP と、NN 個の非負整数 Ai(1iN)A_i(1 \le i \le N) と、N1N - 1 個の ```+```, ```-```, ```*```, ```/``` いずれかからなる文字列 SS が与えられます。
SSj(1jN1)j(1 \le j \le N - 1) 文字目を operatorjoperator_j としたときに、以下の値を計算して出力してください。
mod  P\mod P 上の ((((A1 operator1 A2) operator2 A3) operator3 AN1) operatorN1 AN)(( \dots ((A_1\ operator_1\ A_2)\ operator_2\ A_3)\ operator_3 \dots \ A_{N-1})\ operator_{N-1}\ A_N)
言い換えると、演算子に関わらず計算順序は前からとして計算してください。
ただし、 mod  P\mod P 上の割り算 p/q は、 pqr(mod  P)p \equiv qr (\mod P) かつ 0r<P0 \le r < P である唯一の整数 rr が解であるものとします。

入力

P NP\ N
A1 A2  ANA_1\ A_2\ \dots\ A_N
SS

2P1092 \le P \le 10^9
1N1051 \le N \le 10^5
PP は素数
1Ai<P1 \le A_i < P
S=N1|S| = N - 1
SS+, -, *, / のみからなる

出力

一行に答えを出力せよ。最後に改行せよ。

サンプル

サンプル1
入力
11 10
1 5 5 2 3 4 6 5 2 8
++*--//*-
出力
4

mod  11\mod 11 上での
((((1+5+5)×234)/6)/5)×28((((1+5+5) \times 2-3-4)/6)/5) \times 2-8
を求めてください。可読性向上のため無くても意味が変わらないカッコは省いています。

出典

YSF Beginner Contest: E - modular arithmetic
writer: null
tester: butsuri_0523
HackerRank の規約に基づいて移植されました。一部サイトの都合などで改変したところがあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。