#include<iostream>
#include<cstring>
using namespace std;
int t,n,k,f[1001],sum[1001];
int mod=10000;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>k;
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k+1;j++)sum[j]=sum[j-1]+f[j-1],sum[j]%=mod;
for(int j=0;j<=k;j++)f[j]=(sum[j+1]-sum[j,max(0,j-i+1)]+mod)%mod;
}
cout<<f[k]<<endl;
}
}

├ 测试数据 01：答案正确... (0ms, 8244KB)

├ 测试数据 02：答案正确... (0ms, 8244KB)

├ 测试数据 03：答案正确... (0ms, 8244KB)

├ 测试数据 04：答案正确... (0ms, 8244KB)

├ 测试数据 05：答案正确... (0ms, 8244KB)

├ 测试数据 06：答案正确... (0ms, 8244KB)

├ 测试数据 07：答案正确... (0ms, 8244KB)

├ 测试数据 08：答案正确... (0ms, 8244KB)

├ 测试数据 09：答案正确... (0ms, 8244KB)

├ 测试数据 10：答案正确... (0ms, 8244KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 8244KB

DP秒杀了

DP方程：f:=((f-f+10000)mod 10000+f)mod 10000;

有一个十分强大的规律，把4的写完就有了......

这样的题不会就要多写写，找规律递推就行了

递推式：

f:=(f+f-f) mod 10000;

f表示i时，逆序对长度是j的时候的个数

procedure main;

begin

f[1,0]:=0;f[2,1]:=1;

for i:=2 to l do f:=1;

for i:=3 to l do

begin

m:=(i*(i-1))div 2;

for j:=1 to (m div 2) do

begin

f:=(f+f-f) mod 10000;

if f

仔细想想就是大水题一个。注意到若已有N-1个数，新加入N时，若加在最前，逆序对数目增加N-1，若插在最后，逆序对数目增加0。即插入第I个节点时，增加的逆序对数目为0~I。动态规划轻松搞定。设F(i,j)为第I个数逆序对数目为J时有多少种搞法。显而易见的有F(i,j)=SUM(F(i,j):F(i,j-i+1))（符号打不出来，我用的Excel表示法……）DP[n,k]就是答案。但这样复杂度为O(N^3)，会超时，在这里设置一个Sum数组用于存储F(i,0)到F(i,j)的和，计算就会快了好多。另外注意取模的时候别搞出来负数。

program T1063_1;

const mo=10000;

var t,n,k,i,j,loop:longint;

sum:array[1..1000,-1000..1000]of longint;

begin read(t);

for loop:=1 to t do

begin

read(n,k);

fillchar(sum,sizeof(sum),0);

for i:=0 to k do sum[1,i]:=1;

for i:=2 to n do

for j:=0 to k do

sum:=((sum-sum+mo)mod mo+sum)mod mo;

writeln((sum[n,k]-sum[n,k-1]+mo)mod mo);

end;

end.

超详细题解传送门：

http://user.qzone.qq.com/1304445713/blog/1351823901

整个递推过程的分析都有

不设访问权限，没有动画，没有音乐，很整洁就一个博客而已！