問題一覧 > 通常問題

No.1574 Swap and Repaint

レベル : / AI推定難易度 : 2850 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 7
作問者 : PCTprobability / テスター : KoD
お気に入りにしたユーザー ProblemId : 6267 / 自分の提出
問題文最終更新日: 2021-07-18 03:25:38
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
灘校文化祭コンテスト 2021 day2 (順位表) の他の問題:

Note

The time limit for this problem is $10$ sec. The writer's solution (C++) runs in $2836$ ms.

Problem Statement

PCT came up with the following problem.

Repaint

Balls are placed on a number line.

At coordinate $i \, (i = 1, 2, \dots, N)$, there are $A_i$ red balls and $(2-A_i)$ blue balls. Balls are distinguished even if they are at the same coordinate and have the same color.

There are no balls anywhere else.

Choose $1$ permutation $p$ of length $(N-1)$. Then, for each integer $i$ between $1$ and $(N-1)$, inclusive, perform the following operation.

  • Choose $1$ ball at coordinate $(p_i+1)$. Let $X$ be the color of the chosen ball.

  • Choose $1$ ball at coordinate $p_i$ and repaint the chosen ball with color $X$.

Over all $2^{2(N-1)} \times (N-1)!$ possible ways to perform the operations, find the sum of the number of red balls among the $2N$ balls after the operations, $\bmod 998244353$.

Here, two ways to perform the operations are considered different if the chosen permutations $p$ differ, or if any of the balls chosen during the operations differ.

However, someone has rearranged the values of $A_i$. Therefore, the problem was changed as follows.

Swap and Repaint

Solve the following problem for $S=0,1,...,N$.

Problem

Repeat the following $S$ times: choose $2$ adjacent elements of $A$ and swap them.

For all $(N-1)^S$ ways of rearranging, solve Repaint for the rearranged $A$, and find the sum of the answers, $\bmod 998244353$.
Solve Swap and Repaint.

Input

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

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

Output

Solve Swap and Repaint.

The output consists of $N+1$ lines. On line $i \, (1 \le i \le N+1)$, print the answer for $S=i-1$.

Sample

Sample 1
Input
3
0 1 2
Output
132
228
420
804

When $S=0$, it suffices to solve Repaint for $A = (0, 1, 2)$.

For example, with $p=(1,2)$, performing the operations in the following order results in $4$ red balls after the operations.

  • Choose the red ball at coordinate $p_1 + 1 = 2$ and the blue ball at coordinate $p_1 = 1$. Repaint this blue ball red.
  • Choose the red ball at coordinate $p_2 + 1 = 3$ and the red ball at coordinate $p_2 = 2$. The color of the ball does not change.

    • After the $2$ operations, there are then $1$ red ball at coordinate $1$, $1$ red ball at coordinate $2$, and $2$ red balls at coordinate $3$, for a total of $4$.

    The sum of the answers over all cases is $132$, so print $132$ on line $1$.

    Note that when $S=2$, there are $2$ ways of rearranging that result in $A = (0, 1, 2)$, and these $2$ ways are distinguished.

    Sample 2
    Input
    5
0 1 2 0 1
    Output
    27536
103424
406368
1615760
6446032
25739056

    Sample 3
    Input
    15
2 0 1 0 1 1 2 2 0 0 2 0 1 1 0
    Output
    523214357
664692542
837880257
504621457
945832393
772710139
238318330
459847588
223465057
192424051
725446536
541034409
387888351
350563535
198609141
134414344

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