No.992 最長増加部分列の数え上げ
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 :
%20
/ テスター :
kotatsugame
タグ : / 解いたユーザー数 78
作問者 :
%20
/ テスター :
kotatsugame
問題文最終更新日: 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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。