O(NK^2)的算法是果果的，O(NK)的算法只要用一个TOT来计算前缀和就可以了，边界+-1搞了一会儿就A了。
program p2431; var x:array[0..1,0..1000] of longint; n,k,i,j,tot,k1,k2:longint; begin readln(n,k); fillchar(x,sizeof(x),0); x[0,0]:=1; for i:=1 to n do begin k1:=i mod 2; k2:=1-k1; x[k1,0]:=x[k2,0]; tot:=x[k2,0]; for j:=1 to k do begin if j<i then tot:=(tot+x[k2,j]) mod 10000 else tot:=(tot-x[k2,j-i]+x[k2,j]+10000) mod 10000; x[k1,j]:=tot; end; end; writeln(x[k1,k]); end.
评论 (0)
