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

加入题单

上一题 下一题 算法标签: