51nod 1020 逆序排列 DP
2024-10-15 17:39:01
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。
1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。
1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3
由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。
Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 - T + 1行:每行2个数n,k。中间用空格分隔。(2 <= n <= 1000, 0 <= k <= 20000)
Output
共T行,对应逆序排列的数量 Mod (10^9 + 7)
Input示例
1
4 3
Output示例
6
相关问题
思路:
设dp[i][j]表示1-i的全排列中逆序数为j的个数。试想,假如一直dp[i-1]的每一种状态,那么和dp[i]有什么关系。
不难得出,对于已知的dp[i-1]的基础上,插入i就可以得到dp[i]。但是i的位置放置的不同,就影响了dp[i]的每一项。
列出i取值1,2,3,4的每一项,可以得出一个关系式:
得到这个关系式其实这道题目已经可以做了,利用前缀和优化,但是还可以更进一步
同理有:
此时假设k可以取到0,实际上max在这里只是优化
则可以得到:
最后需要注意相减可能为负数,需要加上mod再取mod
代码:
#include <stdio.h>
const int mod=;
int dp[][];
void init() {
for(int i=;i<=;++i) {
dp[i][]=;
}
for(int i=;i<=;++i) {
int maxval=i*(i-)>>;
for(int j=;j<=maxval&&j<=;++j) {
int temp=;
if(j>=i) temp=dp[i-][j-i];
dp[i][j]=((dp[i][j-]+dp[i-][j]-temp)%mod+mod)%mod;
}
}
}
int main() {
init();
int T,n,k;
scanf("%d",&T);
while(T--) {
scanf("%d %d",&n,&k);
printf("%d\n",dp[n][k]);
}
return ;
}
最新文章
- DUT Star Weekly Contest #3 Problem F Solution
- 获取进程CPU占用率
- 大三上 —— IOS五天实训
- SQL Server 的数据库简单操作
- this.down和this.up用法
- Windows Platform Predefined Macros
- DOS下删除整个目录及下属所有文件夹及文件最好用的命令
- 2015年10月22日CSS学习笔记
- UITableView编写可以添加,删除,移动的物品栏(一)
- 用window.print()打印指定div里面的内容
- ETL的经验总结
- js 基础对象一
- Python人工智能之-三大数学难点 !
- 图解HTTP笔记
- 对象的get set方法
- SNF.Net 快速开发平台Spring.Net.Framework 诞生的由来与规划
- English trip -- Review Unit6 Time 时间
- bash 环境配置及脚本
- 简单的互斥同步方式——synchronized关键字详解
- gdb调试行号错位
热门文章
- LeetCode 346. Moving Average from Data Stream (数据流动中的移动平均值)$
- 利用cookies+requests包登陆微博,使用xpath抓取目标用户的用户信息、微博以及对应评论
- iOS之 git 简单使用
- 如何获取系统Home(Launcher)应用判断用户是否处于home界面
- Xilinx ISE14.1用Verilog语言实现一个半加器并测试
- robotframework自动化:登陆操作
- D3.js使用过程中的常见问题(D3版本D3V4)
- netty常用使用方式
- ab使用命令
- 在C#中interface与abstract class的区别