program vijos3;

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

f : array[0..201,0..201] of longint;

begin

readln(m,n);

for i := 1 to m do

begin

f := 1;

for j := 1 to i-1 do

if j > n then break else

f := ( f * (i-j) mod 2009 + f * ( j + 1 ) mod 2009) mod 2009;

end;

writeln(f[m,n])

end.

为什么我的过不了。貌似方程式一样的吧。。。。。。。那位大牛能指点一下。。。。

f表示前i个数有j个链，最后一个数是第k大的方案总数，转移可以枚举前一个数是第几大的，但这样是n^4的，可以用后缀、前缀和优化到O(n^3)

这个题目用seekeof、read都会wa……………………

VJ系统有BUG，seekeof会0分。

这题有两种DP方法，一种是考虑第一个数填什么数，第二种是考虑n这个数填在哪

我觉得第三题解题报告的方程有问题，谁贴个标程上来吧。。。

我是这样想的。

F[N,K]表示N个车厢需要用K个链子的方案数。

即在N的全排列中寻找若干种排列，使得该排列中顺序存在K+1个上升段。

那么F[N,k+1]=F[N-1,k+1]*(k+1)+F[n-1,k]*(n-k);

K全部退一位就是F=F*j+F[i-1,j-1)*(i-j+1);

输出F[n,k+1]

ANDY_XU：

那个MOD 2009为什么可以写在语句里？

我敲过一些数据。写在最后F[n,k] mod 2009才是正确的啊。

笨笨。样例有问题。。。

LS的。你把mod运算去掉之后运行 10 4这组数据，看你得出来的和我以不一样！

事实证明。加上mod运算之后都是一样的。。。这让我囧到了。。。

但是我拿我AC的程序来运行10 4 这组数据，反而是错的

var

f:array[0..200,0..200]of qword;

n,k,i,j:longint;

begin

while not eof do

begin

fillchar(f,sizeof(f),0);

readln(n,k);

inc(k);

f[0,1]:=1;

for i:=1 to n do

for j:=1 to k do

f:=(f*j+f*(i-j+1)) mod 2009;

writeln(f[n,k]);

end;

end.

AC了。

我理解了为什么不能放最后了。。原因很简单。。。

Qword可能不够存下那些数字溢出了。。。

比赛时50分,再一测就AC了!!!!!!

0分的牛们。。。太诡异了，seekeof=0分，eof=100

Var

p:array[0..300,0..300] of Qword;

i,j,n,k:integer;

Begin

fillchar(p,sizeof(p),0);

p[0,0]:=0;

p[1,0]:=1;

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

p[3,0]:=1;p[3,1]:=4;p[3,2]:=1;

for i:=4 to 200 do

for j:=0 to i-1 do

if (j=0) then p:=1

else p:=(p*(i-j)+p*(j+1)) mod 2009;

while not eof do

begin

readln(n,k);

writeln(p[n,k]);

end;

End.

满分标程，楼下的纯粹不懂装懂~~还DP。。。。。

我是先用组合生成法，打表计算了n

依然是慢了...我的苯苯啊...