#1790. 栞

    ID: 1790 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1417来源:qoj.ac数据:公开样例组合数学

栞

栞

题目描述

标题: 栞 - Problem - QOJ.ac

#7766. 栞

Statistics

The problem was used in the following contests:

给定 n,k,设 p 是一个 n 阶排列,你可以将 p 划分成恰好 k 个非空连续段(也即,选择 k−1 个断点 1≤x1<x2<⋯<xk−1<n,令划分为 [1,x1],(x1,x2],⋯,(xk−1,n]),然后将每段内部的数从小到大排序,得到一个新的排列 q。

定义 f(p) 表示,所有划分方案里可能得到的 q 中字典序最小的那一个。

现在给定一个 n 阶排列 q,求有多少个 n 阶排列 p 的 f(p)=q。请输出答案模 998244353 的值。

输入格式

第一行两个数 n,k。

第二行 n 个数,表示排列 q。

输出格式

一行一个数,表示答案。

样例

样例 1
2 1
1 2
2
样例 2
3 3
3 1 2
1
样例 3
6 3
1 2 3 6 5 4
13

数据范围

对于所有数据,1≤n≤500,1≤k≤n。

子任务 1(10%):n≤6。

子任务 2(20%):n≤10。

子任务 3(30%):q=(1,2,⋯,n)。

子任务 4(40%):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1
1 2
2

样例 2

6 3
1 2 3 6 5 4
13