No.2513 Power Eraser
タグ : / 解いたユーザー数 20
作問者 : 👑
amentorimaru
/ テスター :
cleantted
PCTprobability
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もしくは右上の雲マークをクリックしてアカウントを作成してください。