No.2556 Increasing Matrix
レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : 👑
箱
/ テスター :
hotman78
タグ : / 解いたユーザー数 20
作問者 : 👑
箱
/ テスター :
hotman78
問題文最終更新日: 2023-11-30 08:34:43
問題文
成分が正の整数である $N$ 次正方行列であって、次の条件を満たすものは何通りありますか。$998244353$ で割った余りを求めてください。
- 各行について広義単調増加
- 各列について広義単調増加
- $i=1,2,\ldots,N$ に対して、$(i,i)$ 成分は $A_i$ である
制約
- $1\le N\le 10^5$
- $1\le A_1\le A_2\le\cdots\le A_N\le 10^9$
- 入力はすべて整数
入力
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
出力
行列の個数を $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
3 1 2 3
出力
64
以下は条件をみたす行列の一例です。
$$ \begin{pmatrix} 1 & 1 & 3 \\ 2 & 2 & 3 \\ 2 & 2 & 3 \end{pmatrix} $$サンプル2
入力
1 5
出力
1
サンプル3
入力
9 101 298 385 414 582 651 775 823 958
出力
789729159
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。