No.2144 MM

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

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

問題一覧 > 通常問題

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

milkcoffee / テスター :

first_vil

nok0

10 ProblemId : 8776 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-11-25 22:34:15

問題文

正整数 $N,M$ が与えられます。

与えられた $N,M$ に対して、 良い数列 を以下のように定義します。

長さ $N$ であり、各要素が $0$ 以上 $M-2$ 以下である。
以下の操作を繰り返す(何回でも良い)ことで、全ての要素を $M$ の倍数にすることができる。

隣接する $2$ 要素を選び、それぞれに $1$ を加算する。

長さ $N$ の非負整数列 $A$ が与えられるので、それが良い数列かどうかを判定してください。

また、良い数列だった場合は、良い数列の中で辞書順で何番目かを $998244353$ で割ったあまりを求めてください。

入力

 $N$   $M$ 
 $A_1$   $A_2$   $\cdots$   $A_N$

$2 \leq N \leq 2 \times 10^5$
$3 \leq M \leq 10^6$
$0 \leq A_i \leq M-2$ $(1 \leq i \leq N)$
入力は全て整数である

出力

非負整数列 $A$ が良い数列であれば、それが良い数列の中で辞書順で何番目かを $998244353$ で割ったあまりを整数で出力してください。
良い数列でなければ -1 を出力してください。

サンプル

サンプル1

入力

3 5
2 0 3

出力

$N=3,M=5$ であるとき、良い数列を辞書順に $8$ 番目まで並べると以下のようになります。
$(0,0,0),(0,1,1),(0,2,2),(0,3,3),(1,1,0),(1,2,1),(1,3,2),(2,0,3)$

$(2,0,3)$ に対して「 $1,2$ 番目の要素に $1$ を加算する」という操作を $3$ 回行うと $(5,3,3)$ になります。
そして、 $(5,3,3)$ に対して「 $2,3$ 番目の要素に $1$ を加算する」という操作を $2$ 回行うと $(5,5,5)$ になります。
全ての要素を $5$ の倍数にすることができたため、 $(2,0,3)$ は良い数列と言えます。

サンプル2

入力

2 1000000
0 1

出力

-1

$1,2$ 番目の要素の両方を $1000000$ の倍数にすることはできないため、 $(0,1)$ は良い数列ではないです。

サンプル3

入力

15 840067
703190 347257 169927 111976 170201 451648 473561 341367 803725 263056 785072 155864 274520 420688 391794

出力

293678726

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