bzoj 2431 [HAOI2009]逆序对数列

bzoj 2431 [HAOI2009]逆序对数列

​​ Description 对于一个数列{ai}，如果有i< j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的 数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？ Input 第一行为两个整数n，k。

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

Sample Input 4 1 Sample Output 3

样例说明： 下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4； 100%的数据 n<=1000，k<=1000

HINT 33 Source Day1

[Submit][Status][Discuss] 设dp[i][j]表示1~i的排列 逆序对数量为j的情况下 个数有多少

转移很好想

但是朴素是n^3 那么不妨我们将转移重写表示成从前面转移来的形式 这样即可前缀和优化

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int mod=10000;inline int inc(int x,int v){ return x+v>=mod?x+v-mod:x+v;}inline int dec(int x,int v){ return x-v<0?x-v+mod:x-v;}const int N=1100;int dp[N][N],s[N][N],n,k;int main(){ freopen("bzoj2431.in","r",stdin); n=read();k=read(); for (int i=1;i<=n;++i){ dp[i][0]=s[i][0]=1; for (int j=1;j<=k;++j){ if (i>j) dp[i][j]=s[i-1][j]; else dp[i][j]=dec(s[i-1][j],s[i-1][j-i]); s[i][j]=inc(s[i][j-1],dp[i][j]); } }printf("%d\n",dp[n][k]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。