#P2776. 斩草除根

    ID: 1883 传统题 1000ms 512MiB 尝试: 11 已通过: 8 难度: 6 上传者: 标签>CF2100提高冒泡排序双射计数乘法原理补集计数高精度乘法高精度减法

斩草除根

题目描述

对 使用 kk 轮冒泡排序后有序的长度为 nn 的排列计数。

答案不取模,请注意实现方式。

对长度为 nn 的排列 aa 的第 ii 轮冒泡排序定义为:

for(int j=1;j<=n-i;j++)
	if(a[j]>a[j+1])
		swap(a[j],a[j+1]);

输入格式

一行两个整数 n,kn,k。

输出格式

一行一个整数表示你的答案。

8 5
10920

数据规模与约定

对于 100%100\% 的数据,1≤n≤5×1031\leq n\leq 5\times 10^3,0<k<n0<k<n,答案的长度不超过 2×1042\times 10^4。