No.2793 Mancala Master

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 :

箱星 / テスター :

dadas

2 ProblemId : 10465 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-06-23 08:40:59

正整数列 $A=(A_1,\ldots,A_N)$ と正整数 $K$ が与えられます。

小星さんは次のようなゲームを行います。はじめスコアは $1$ とし、 $i=1,2,\ldots,N$ に対して座標 $i$ に石を $A_i$ 個置きます。

$i=N,N-1,\ldots,1$ の順に次の操作を行います。

座標 $i$ にあるすべての石を座標 $0,1,\ldots,i-1$ のいずれかに動かす。座標 $j$ に動かす石の個数を $c_j$ とするとき、スコアに $f(c_0)f(c_1)\cdots f(c_{i-1})$ をかける。ここで $f(m)=\begin{cases} K^m-K^{m-1} & (m>0) \\ 1 & (m=0) \end{cases}$ である。

可能な操作方法すべてについての最終的なスコアの総和を $998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられます。

 $T$ 
 $\mathrm{case}_1$ 
 $\vdots$ 
 $\mathrm{case}_T$

各ケースは以下の形式で与えられます。

 $N$   $K$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

$T$ 行出力してください。 $i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

1
2 10
1 2

まず座標 $2$ にある $2$ 個の石を動かします。

$2$ 個とも座標 $0$ に動かしたとき、スコアに $10^2-10=90$ をかけます。次に座標 $1$ にある $1$ 個の石を座標 $0$ に動かし、スコアに $10-1=9$ をかけます。
$2$ 個とも座標 $1$ に動かしたとき、スコアに $10^2-10=90$ をかけます。次に座標 $1$ にある $3$ 個の石を座標 $0$ に動かし、スコアに $10^3-10^2=900$ をかけます。
$1$ 個ずつ座標 $0,1$ に動かしたとき、スコアに $(10-1)(10-1)=81$ をかけます。次に座標 $1$ にある $2$ 個の石を座標 $0$ に動かし、スコアに $10^2-10=90$ をかけます。

よってスコアの総和は $90\times 9+90\times 900+81\times 90=89100$ です。

2
1 2
3
3 3281572
842184 12484 58238890

4
724046312

$998244353$ で割った余りを求めてください。

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