問題一覧 > 通常問題

No.2556 Increasing Matrix

レベル : / AI推定難易度 : 3000 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 19
作問者 : 👑 箱星 / テスター : hotman78
お気に入りにしたユーザー ProblemId : 9423 / 自分の提出
問題文最終更新日: 2024-08-10 10:19:26
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
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

How many square matrices of order $N$ whose entries are positive integers satisfy the following conditions? Find the count modulo $998244353$.

  • Each row is weakly increasing
  • Each column is weakly increasing
  • For $i=1,2,\ldots,N$, the $(i,i)$ entry is $A_i$

Constraints

  • $1\le N\le 10^5$
  • $1\le A_1\le A_2\le\cdots\le A_N\le 10^9$
  • All input values are integers

Input

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

Output

Output the number of matrices modulo $998244353$.

Sample

Sample 1
Input
3
1 2 3
Output
64

The following is an example of a matrix satisfying the conditions.

$$ \begin{pmatrix} 1 & 1 & 3 \\ 2 & 2 & 3 \\ 2 & 2 & 3 \end{pmatrix} $$
Sample 2
Input
1
5
Output
1

Sample 3
Input
9
101 298 385 414 582 651 775 823 958
Output
789729159

Output the answer modulo $998244353$.

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