102676: [AtCoder]ABC267 G - Increasing K Times
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
You are given an integer sequence $A = (A_1, \dots, A_N)$ of length $N$.
Find the number, modulo $998244353$, of permutations $P = (P_1, \dots, P_N)$ of $(1, 2, \dots, N)$ such that:
- there exist exactly $K$ integers $i$ between $1$ and $(N-1)$ (inclusive) such that $A_{P_i} \lt A_{P_{i + 1}}$.
Constraints
- $2 \leq N \leq 5000$
- $0 \leq K \leq N - 1$
- $1 \leq A_i \leq N \, (1 \leq i \leq N)$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
4 2 1 1 2 2
Sample Output 1
4
Four permutations satisfy the condition: $P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3)$.
Sample Input 2
10 3 3 1 4 1 5 9 2 6 5 3
Sample Output 2
697112
Input
题意翻译
**题目描述** 给定一个正整数序列 $A=(a_1,a_2,\ldots,a_n)$，问有多少个 $1\sim n$ 的排列 $P=(p_1,p_2,\ldots,p_n)$ 满足： - 存在恰好 $k$ 个整数 $i(1\leqslant i\leqslant n-1)$ 满足 $a_{p_i}<a_{p_{i+1}}$ 对 $998244353$ 取模。 **输入格式** 第一行两个整数 $n,k$，含义如题意所示。 第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。 **输出格式** 输出一个整数，表示满足条件的排列 $P$ 个数。 **数据范围** $2\leqslant n\leqslant 5000,0\leqslant k\leqslant n-1,1\leqslant a_i\leqslant n$ **样例解释** 只有四个排列 $P$ 满足条件，分别是 $(1,3,2,4),(1,4,2,3),(2,3,1,4),(2,4,1,3)$。Output
分数：$600$分
问题描述
给你一个长度为$N$的整数序列$A = (A_1, \dots, A_N)$。
找出满足以下条件的排列$P = (P_1, \dots, P_N)$的数量，对$998244353$取模：
- 在$1$到$(N-1)$（包括）之间的整数$i$恰好有$K$个，使得$A_{P_i} \lt A_{P_{i + 1}}$。
约束条件
- $2 \leq N \leq 5000$
- $0 \leq K \leq N - 1$
- $1 \leq A_i \leq N \, (1 \leq i \leq N)$
- 输入中的所有值都是整数。
输入
从标准输入以以下格式获取输入：
$N$ $K$ $A_1$ $\ldots$ $A_N$
输出
打印答案。
样例输入1
4 2 1 1 2 2
样例输出1
4
有四个排列满足条件：$P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3)$。
样例输入2
10 3 3 1 4 1 5 9 2 6 5 3
样例输出2
697112