华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 947|回复: 0
打印 上一主题 下一主题

P1521 求逆序对

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2019-10-23 20:25:26 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
https://www.luogu.org/problem/P1521

题目描述
我们说(i,j)是a1,a2,…,aN的一个逆序对当且仅当i<j且ai>a j。例如2,4,1,3,5的逆序对有3个,分别为(1,3),(2,3),(2,4)。现在已知N和K,求1…N的所有特定排列,这些排列的逆序对的数量恰好为K。输出这些特定排列的数量。

例如N=5,K=3的时候,满足条件的排列有15个,它们是:

1,2,5,4,3   
1,3,4,5,2   
1,3,5,2,4   
1,4,2,5,3   
1,4,3,2,5   
1,5,2,3,4   
2,1,4,5,3   
2,1,5,3,4   
2,3,1,5,4   
2,3,4,1,5
2,4,1,3,5   
3,1,2,5,4   
3,1,4,2,5   
3,2,1,4,5   
4,1,2,3,5
输入格式
输入第一行有两个整数N和K。(N≤100,K≤N*(N-1)/2)

输出格式
将1…N的逆序对数量为K的特定排列的数量输出。为了避免高精度计算,请将结果mod 10000以后再输出!

输入输出样例
输入
5 3
输出
15

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:42 , Processed in 0.097122 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表