問題一覧 > 通常問題

No.1574 Swap and Repaint

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : PCTprobabilityPCTprobability / テスター : KoDKoD
2 ProblemId : 6267 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-18 03:25:38

注意

この問題の実行時間制限は $10$ sec です。Writer解(C++)の実行時間は $2836$ ms です。

問題文

PCT 君は以下のような問題を考えました。

Repaint

数直線上にボールが置かれています。

座標 $i \, (i = 1, 2, \dots, N)$ には $A_i$ 個の赤いボールと $(2-A_i)$ 個の青いボールが置かれています。同じ座標に同じ色のボールがあったとしても区別します。

これら以外の場所にはボールは置かれていません。

長さ $(N-1)$ の順列 $p$ を $1$ つ選びます。そして、$1$ 以上 $(N-1)$ 以下の各整数 $i$ に対して以下の操作を行います。

  • 座標 $(p_i+1)$ にあるボールを $1$ つ選ぶ。選んだボールの色を $X$ とする。

  • 座標 $p_i$ にあるボールを $1$ 個選び、選んだボールの色を $X$ に塗り替える。

あり得る操作 $2^{2(N-1)} \times (N-1)!$ 通り全てに対して、操作後のボール $2N$ 個のうち赤いものの個数の総和を $\bmod 998244353$ で求めてください。

ただし、二つの操作が異なるとは、選んだ順列 $p$ が異なるか、操作の途中で選ぶいずれかのボールが異なることとします。

しかし、何者かによって $A_i$ の値が並び替えられてしまいました。そこで、問題を以下のように変更しました。

Swap and Repaint

$S=0,1,...,N$ に対して以下の問題を解いてください。

問題

$A$ の隣り合う $2$ 要素を選び入れ替えることを $S$ 回繰り返します。

$(N-1)^S$ 通り全ての並び替え方について、並び替えた後の $A$ に対して Repaint を解き、解の総和を $\bmod 998244353$ で求めてください。

Swap and Repaint を解いてください。

入力

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

  • 入力は全て整数である。
  • $2 \le N \le 10^5$
  • $0 \le A_i \le 2$

出力

Swap and Repaint を解いてください。

出力は $N+1$ 行に渡ります。$i \, (1 \le i \le N+1)$ 行目には $S=i-1$ のときの解答を出力してください。

サンプル

サンプル1
入力
3
0 1 2
出力
132
228
420
804

$S=0$ のとき、$A = (0, 1, 2)$ に対して Repaint を解けばよいです。

例えば、$p=(1,2)$ としたとき、次の順に操作をすると操作後の赤いボールの個数は $4$ 個となります。

  • 座標 $p_1 + 1 = 2$ にある赤いボールと座標 $p_1 = 1$ にある青いボールを選ぶ。この青いボールを赤く塗り替える。
  • 座標 $p_2 + 1 = 3$ にある赤いボールと座標 $p_2 = 2$ にある赤いボールを選ぶ。ボールの色は変わらない。
  • すると $2$ 回の操作が終わった後座標 $1$ には $1$ 個の赤いボール、座標 $2$ には $1$ 個の赤いボール、座標 $3$ には $2$ 個の赤いボールがあるため合計は $4$ 個です。

    全ての場合についての解の総和は $132$ なので $1$ 行目には $132$ を出力します。

    なお、$S=2$ のとき $A = (0, 1, 2)$ となるような並び替え方は $2$ 通りありますが、この $2$ 通りは区別することに注意してください。

    サンプル2
    入力
    5
    0 1 2 0 1
    出力
    27536
    103424
    406368
    1615760
    6446032
    25739056

    サンプル3
    入力
    15
    2 0 1 0 1 1 2 2 0 0 2 0 1 1 0
    出力
    523214357
    664692542
    837880257
    504621457
    945832393
    772710139
    238318330
    459847588
    223465057
    192424051
    725446536
    541034409
    387888351
    350563535
    198609141
    134414344

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