No.992 最長増加部分列の数え上げ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 55
作問者 : %20%20 / テスター : kotatsugamekotatsugame
5 ProblemId : 3784 / 出題時の順位表
問題文最終更新日: 2020-03-08 16:57:30

問題文

$N$ 要素からなる整数列 $A=(A_1,A_2,\cdots,A_N)$ が与えられます。
$A$ の最長増加部分列の取り出し方の総数を求めてください。
取り出した部分列が列として等しい場合でも、選んだ位置の集合が異なれば別の取り出し方として数えます。

すなわち、$1\le I_1\lt I_2\lt\cdots\lt I_M\le N$ かつ $A_{I_1}\lt A_{I_2}\lt\cdots\lt A_{I_M}$ となるような整数列 $I$ のうち、要素数 $M$ が最大になるようなものが何通りあるかを求めてください。

ただし、答えを $10^9+7$ で割った余りを出力してください。

入力

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

入力は以下の制約を満たします。

  • $N,A_i$ は整数である
  • $1\le N\le2\times 10^5$
  • $-10^9\le A_i\le10^9$

出力

$A$ の最長増加部分列の取り出し方の総数を $10^9+7$ で割った余りを出力してください。

サンプル

サンプル1
入力
5
1 4 2 5 3
出力
3

最長増加部分列の取り出し方は、次の $3$ 通りです。

  • $(A_1,A_2,A_4)=(1,4,5)$
  • $(A_1,A_3,A_4)=(1,2,5)$
  • $(A_1,A_3,A_5)=(1,2,3)$
サンプル2
入力
3
1 1 2
出力
2

最長増加部分列の取り出し方は、次の $2$ 通りです。これらは別のものとして数えることに注意してください。

  • $(A_1,A_3)=(1,2)$
  • $(A_2,A_3)=(1,2)$
サンプル3
入力
12
1 1 2 2 3 1 2 4 3 3 4 4
出力
40

$(1,2,3,4)$ という部分列がいっぱいあります。

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