首页 > 代码库 > BZOJ 2431 HAOI2009 逆序对数列 递推
BZOJ 2431 HAOI2009 逆序对数列 递推
题目大意:求1~n的所有排列中有多少种逆序对为k的方案数
令f[i][j]为前i个数的排列中逆序对数为j的方案数
那么我们将第i个数插入1~i-1的排列中 可以产生0~i-1个逆序对
于是有
f[i][j]=Σf[i-1][k] (j-i+1<=k<=j)
维护前缀和即可
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 1010 #define MOD 10000 using namespace std; int n,k; int f[M][M],g[M][M]; int main() { int i,j; cin>>n>>k; f[0][0]=1; for(i=0;i<=k;i++) g[0][i]=1; for(i=1;i<=n;i++) for(j=0;j<=k;j++) { if(j>=i) f[i][j]=(g[i-1][j]-g[i-1][j-i]+MOD)%MOD; else f[i][j]=g[i-1][j]; g[i][j]=(j?g[i][j-1]:0)+f[i][j]; g[i][j]%=MOD; } cout<<f[n][k]<<endl; }
BZOJ 2431 HAOI2009 逆序对数列 递推
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。