华师一附中OI组

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

P2513 [HAOI2009]逆序对数列

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

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

题目描述
对于一个数列{ai},如果有i<j且ai>aj,那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列,可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个?

输入格式
第一行为两个整数n,k。

输出格式
写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。

输入输出样例
输入
4 1
输出
3
说明/提示
样例说明:

下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;

测试数据范围

30%的数据 n<=12

100%的数据 n<=1000,k<=1000

回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-12-25 15:14 , Processed in 0.104102 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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