問題一覧 > 通常問題

No.16 累乗の加算

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 573
作問者 : yuki2006yuki2006
3 ProblemId : 42 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:26

問題文

Maliaは、与えられた数式を計算しようとしている。
数式は一つの変数\(x\)のみで構成されており、各\(i\)項は\(x\)の\(a_i\)乗で構成されている。
ここで \(x^n\)は\(x\)の\(n\)乗を表すことにすると
\( x^{a_1} + x^{a_2} + \dots + x^{a_N} \)
という形になっている。
\(x\)の累乗を計算するのは大変だと気づいたあなたは、代わりに計算してあげることになりました。

\(x\)と各\(a_i\ (1 \leq i \leq n)\)が与えられた時の計算値を求めてください。
答えの値が非常に大きくなるので計算値に対して\(1,000,003\) で割ったあまりを求めてください。

計算途中の値が32ビットに収まらないことが有ります。

入力

\(x\ N\)
\(a_1\ a_2\ \dots\ a_N\)

\(1\)行目に変数値を表す整数値\(x\ (1 \leq x \leq 100)\)と項の数を表す整数値\(N\ (1 \leq N \leq 100)\)が半角スペース区切りで与えられる。
\(2\)行目には、各項の指数値を表す整数値 \(a_i\ (0 \leq a_i \leq 100,000,000)\)が半角スペース区切りで与えられる。

出力

\(x^{a_1} + x^{a_2} + \dots + x^{a_N}\) の計算値を \(1,000,003\) で割ったあまりを求めてください。

サンプル

サンプル1
入力
2 3
1 2 3
出力
14

\(x + x^2 + x^3 , x=2\) を表しております。なのでこの計算値はこのようになります。
\(x + x^2 + x^3 = 2 + 4 + 8 = 14\)

サンプル2
入力
2 2
0 100
出力
253110

\(x^0 + x^{100} = 1 + 1267650600228229401496703205376 = 1267650600228229401496703205377\)
となるが、\(1,000,003\) で割ったあまりは、\(253110\)となる。

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