#P4621. Tc605

    ID: 3297 传统题 1000ms 128MiB 尝试: 395 已通过: 173 难度: 9 上传者: 标签>CF2600省选/NOI-不变量分析最近更大/更小元素线性 DP计数 DP前缀和优化 DP滚动数组TC605

Tc605

题目描述

最初你有一个长度为 N 的数字序列 A。为了方便起见,序列 A 是一个排列。 你可以操作最多 K 次。每一次操作你可以先选定一个 A 的一个子串,然后将这个子串的数字全部变成原来这个子串的最大值。问最终有几种可能的数字序列。答案对 1e9+7 取模。

输入格式

第一行两个数 N 和 K。第二行 N 个数,描述一个排列 A。 N,K<=500, 有6组数据N>100,有梯度

输出格式

输出一个数,表示答案在模域下的值。

3 2 
3 1 2
4

提示

没有写明提示

题目来源

TC 605 Hard