题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2431

考虑新加入一个数i,根据放的位置不同,可以产生0~i-1个新逆序对;

所以f[i][j]可由f[i-1][j-k]相加得到,其中0<=k<=i-1&&k<=j;

再优化一下,每次前缀和减掉最前一个,加上最后一个,保持在合法范围内更新即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,sum;
int f[][],p=; int main(){
scanf("%d%d",&n,&m);
f[][]=;
/*
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<i&&k<=j;k++)
(f[i][j]+=f[i-1][j-k])%=p;
*/
for (int i=;i<=n;i++){
sum=;
for (int j=;j<=m;j++){
if (j>=i)sum=(sum-f[i-][j-i]+p)%p;
(sum+=f[i-][j])%=p;
f[i][j]=sum;
}
}
printf("%d",f[n][m]);
return ;
}

最新文章

  1. Patching Array
  2. 领域模型驱动设计(Domain Driven Design)入门概述
  3. js-设置焦点
  4. linux kernel 字符设备详解
  5. JAVA学习Swing章节流布局管理器简单学习
  6. 学习OpenCV——配置CUDA环境
  7. des算法的C#实现
  8. [转] LCA与Tarjan
  9. 常用google产品
  10. (转)HTML特殊字符
  11. eq,neq,gt,lt等表达式缩写
  12. J2EE应用服务器计数器
  13. Oracle ADDM报告生成和性能分析
  14. Struts2——通配符,Action Method_DMI
  15. DNA甲基化测序方法介绍
  16. postfix 如何设置邮件头翻译的功能
  17. redis 单节点安装
  18. Thread.currentThread()与this的区别
  19. 递归神经网络(Recursive Neural Network, RNN)
  20. C# 动态获取代码所在行号

热门文章

  1. 深究Spring中Bean的生命周期
  2. http://www.cnblogs.com/shihaiming/
  3. TeX系列: tikz-3dplot绘图宏包
  4. 常见的哈希Hash算法 &amp; MD5 &amp; 对称非对称加密 &amp; 海明码
  5. Spring boot 整合spring Data JPA+Spring Security+Thymeleaf框架(上)
  6. TFTP服务器
  7. [CSS3] Understand CSS Selector Specificity
  8. lua 暂停写法
  9. indexOf 和 lastIndexOf 的区别
  10. fetch 函数分装