luogu 2513 逆序对数列

对于1~n的整数组成的的排列，其中逆序对数为K的排列有几种

比如n=4,K=1时

下列3个数列逆序对数都为1，     1 2 4 3 ；1 3 2 4 ；2 1 3 4；

f[i][j]  表示 1~i 的整数组成排列， 逆序对数为 j ，的排列个数

状态转移：

我们在 1~i-1 的某个排列中插入i ，可能贡献  0~i-1 个逆序对

f[i][j] = sum{ f[i-1][j-k] }  ,  0<=k<=min(i-1,j)

  k 即我们枚举的贡献

复杂度O(n* k^2) ,   

超时

#include <iostream>
#include <algorithm>
using namespace std ;
 const int N=2001,mod=10000;
 
 int n,K,f[N][N];
 
 void solve(){
 	int i,j,k;
 	
 	f[1][0]=1;
 	
 	for(i=1;i<=n;i++)
 	 for(j=0;j<=K;j++)
 	  for(k=0;k<=min(i-1,j);k++)
 	   f[i][j]+=f[i-1][j-k],f[i][j]%=mod;
 	cout<<f[n][K];
 }
 signed main(){
 	cin>>n>>K;
 	solve();
 }
 
 

 然后就来了         --- [前缀和]

等价转化一下转移方程：

 f[i][j] = sum{ f[i-1][t] } ,  max(0,i-j+1)

仔细观察这个方程

利用前缀和

维护 f[i-1][t] ,假设其为S ，

使用时直接 f[i][j]=S;   

维护S： S+=f[i-1][t]

#include <iostream>
#include <algorithm>
using namespace std ;
 const int N=1005,mod=10000;
 
 int n,K,f[N][N];
 
 void solve(){
 	int i,j;
 	
 	f[1][0]=1;
 	
 	for(i=2;i<=n;i++){
	  int s=0;
 	 for(j=0;j<=K;j++){
 	 	s+=f[i-1][j]; s%=mod;
 	   f[i][j]=s;
 	   
 	   if(j-i+1>=0) s=(s-f[i-1][j-i+1]+mod)%mod; 
	  }
    }
 	cout<<f[n][K];
 }
 signed main(){
 	cin>>n>>K;
 	solve();
 }
 
 

 这里 f[i][j] = f[i-1][k] 这样的式子就多注意观察了