No.2513 Power Eraser
レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : 👑
amentorimaru
/ テスター :
cleantted
PCTprobability
👑 
Mizar
タグ : / 解いたユーザー数 20
作問者 : 👑
amentorimaru
/ テスター :
cleantted
PCTprobability
👑 Mizar
問題文最終更新日: 2023-10-13 15:15:40
注意
この問題の実行時間制限は $6$ sec です。実行制限時間が厳しいため、高速な言語の使用を強く推奨します。
問題文
エトワーニュくんはバーチャル空間の黒板で勉強会をしています。かしこいですね。かわいいですね。
黒板には $N$ 個の数値が左から $A_1, A_2, \dots , A_N$ と書かれています。
エトワーニュくんは $X$ の数値を覚えながら次の操作を行います。
- 最初エトワーニュくんは $X=1$ を記憶する
- 次の操作を黒板の数値がなくなるまで繰り返す
- 黒板に書いてある好きな要素を一つ選び、この値を $Y$ とする
- 選んだ要素より左にある消されていない要素の個数を $s$ として、 $X$ を $(-1)^{s}$ 倍する
- 選んだ要素を黒板から消す
- まだ消されていない全ての要素の個数を $t$ として、 $X$ を $Y^t$ 倍する
エトワーニュくんが $A_i$ を選ぶ順番は $N!$ 通りありますが、その全てにおける $X$ の和を $998244353$ で割った余りを求めてください。
入力
$N$ $A_1\ A_2\ \dots \ A_N$
- 入力は全て整数
- $1 \le N \le 10^5$
- $0 \le A_i \le 998244352$
また、この問題には以下の制約のケースが evil ケースとして用意されている。evil ケースなので、ジャッジ結果には影響しない。
- 入力は全て整数
- $1 \le N \le 2 \times 10^5$
- $0 \le A_i \le 998244352$
出力
答えを出力せよ。
サンプル
サンプル1
入力
4 2 3 4 5
出力
12
例えば $A_3, A_2, A_1, A_4$の順番に消すとします。
- 最初 $X=1$ です。
- $A_3=4$ を選びます。左には二個の数値があり、消した後全体には三個の数値が残る為 $X=1\times (-1)^2 \times 4^3=64$と更新します。
- $A_2=3$ を選びます。左には一個の数値があり、消した後全体には二個の数値が残る為 $X=64\times (-1)^1 \times 3^2=-576$と更新します。
- $A_1=2$ を選びます。左には数値がなく、消した後全体には一個の数値が残る為 $X=-576\times (-1)^0 \times 2^1=-1152$と更新します。
- $A_4=5$ を選びます。左にも数値はなく、消すと数値が残っていない為 $X=-1152$ のままになります。
従って $X=-1152$ となります。
これらの $24$ 通りの選び方全ての合計は $12$ となります。
サンプル2
入力
9 78 98 66 58 73 8 47 87 55
出力
545150365
サンプル3
入力
20 288 270 339 501 184 69 347 507 735 249 936 16 968 790 728 438 966 595 53 738
出力
274218770
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。