問題一覧 > 通常問題

No.2513 Power Eraser

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : 👑 amentorimaru / テスター : cleantted PCTprobability Mizar
お気に入りにしたユーザー ProblemId : 9737 / 自分の提出
問題文最終更新日: 2023-10-13 15:15:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 409 (順位表) の他の問題:

Notice

The execution time limit for this problem is $6$ sec. Because the time limit is strict, using a fast language is strongly recommended.

Problem Statement

Etowanyu-kun is holding a study session on a blackboard in a virtual space. How smart. How cute.


On the blackboard, $N$ numbers are written, from left to right, as $A_1, A_2, \dots , A_N$.

Etowanyu-kun performs the following operations while remembering the value of $X$.

  • Initially, Etowanyu-kun memorizes $X=1$.
  • Repeat the following operation until no numbers remain on the blackboard.
    • Choose any one element written on the blackboard, and let $Y$ be its value.
    • Let $s$ be the number of unerased elements to the left of the chosen element, and multiply $X$ by $(-1)^{s}$.
    • Erase the chosen element from the blackboard.
    • Let $t$ be the number of all elements not yet erased, and multiply $X$ by $Y^t$.

There are $N!$ orders in which Etowanyu-kun can choose the $A_i$. Find the sum of $X$ over all of these orders, modulo $998244353$.

Input

$N$
$A_1\ A_2\ \dots \ A_N$

  • All inputs are integers.
  • $1 \le N \le 10^5$
  • $0 \le A_i \le 998244352$

In addition, cases with the following constraints are provided as evil cases for this problem. Since they are evil cases, they do not affect the judge result.

  • All inputs are integers.
  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i \le 998244352$

Output

Output the answer.

Sample

Sample 1
Input
4
2 3 4 5
Output
12

For example, suppose the elements are erased in the order $A_3, A_2, A_1, A_4$.

  • Initially, $X=1$.
  • Choose $A_3=4$. There are two numbers to its left, and three numbers remain in total after erasing it, so the value is updated to $X=1\times (-1)^2 \times 4^3=64$.
  • Choose $A_2=3$. There is one number to its left, and two numbers remain in total after erasing it, so the value is updated to $X=64\times (-1)^1 \times 3^2=-576$.
  • Choose $A_1=2$. There are no numbers to its left, and one number remains in total after erasing it, so the value is updated to $X=-576\times (-1)^0 \times 2^1=-1152$.
  • Choose $A_4=5$. There are no numbers to its left either, and no numbers remain after erasing it, so $X=-1152$ stays as it is.

Therefore, $X=-1152$ is obtained.

The total over all $24$ ways of choosing is $12$.

Sample 2
Input
9
78 98 66 58 73 8 47 87 55
Output
545150365

Sample 3
Input
20
288 270 339 501 184 69 347 507 735 249 936 16 968 790 728 438 966 595 53 738
Output
274218770

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