089 - Partitions and Inversions（★7）
Editorial
/ 
ここでは、このアルゴリズムを適用した時に整数の交換が行われる回数をバブルソートの交換回数と定義します。
例えば A = (2, 4, 3, 1) の場合、バブルソートの交換回数は 4 です。
/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点: 7 点
問題文
長さ N の正整数列 A = (A_1,A_2,A_3,\cdots, A_N) が与えられます。
この数列を 1 つ以上の空でない連続した区間に分割する方法は 2^{N-1} 通りありますが、これらのうち次の条件を満たすものの個数を数えてください。
- すべての区間について、その区間内での バブルソートの交換回数 が K 以下である。
ただし、答えは非常に大きくなる可能性があるため、10^9+7 で割った余りを出力してください。
バブルソートの交換回数とは
「"A_i > A_{i+1} であればその 2 数を交換する" という操作を i = 1, 2, \cdots, N-1 の順に行う」ことを 1 回の走査とします。そこで、走査を N-1 回繰り返すことで、数列を昇順にソートできることが知られています。ここでは、このアルゴリズムを適用した時に整数の交換が行われる回数をバブルソートの交換回数と定義します。
例えば A = (2, 4, 3, 1) の場合、バブルソートの交換回数は 4 です。
制約
- 1\leq N\leq 2 \times 10^5
- 0\leq K\leq \frac{N(N-1)}2
- 1\leq A_i\leq 10^9
- 入力はすべて整数
小課題
- (1 点): K=0
- (1 点): N\leq 15
- (1 点): N\leq 800
- (2 点): N\leq 10000
- (2 点): 追加の制約はない。
入力
入力は、以下の形式で与えられます。
N K A_1 A_2 A_3 \cdots A_N
出力
問題文中の条件を満たす分割方法の数を 10^9+7 で割った余りを 1 行に出力してください。
入力例 1
4 0 3 1 4 2
出力例 1
2
\{3\}, \{1,4\}, \{2\} という分割と、\{3\}, \{1\}, \{4\}, \{2\} という分割の 2 通りが条件を満たします。
入力例 2
7 2 5 3 7 2 1 2 3
出力例 2
44
入力例 3
7 0 7 6 5 4 3 2 1
出力例 3
1