← 返回题目列表

AtCoder · typical90_ck

089. 划分和倒置 (★7)

中文机器翻译题面 查看原题

配点: 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} 如果成立,将那两个数进行交换的操作 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. (1 点): K=0
  2. (1 点): N\leq 15
  3. (1 点): N\leq 800
  4. (2 点): N\leq 10000
  5. (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 Street 满足条件。


入力例 2

7 2
5 3 7 2 1 2 3

出力例 2

44

入力例 3

7 0
7 6 5 4 3 2 1

出力例 3

1