#include <cstdio>
#include <cstring>
using namespace std;
const int Mod=2009;
const int N=200+ 50 ;
int a[N][N],n,m;
int main()
{
    memset(a,0,sizeof(a));
    a[1][0]=1;  a[2][0]=1;a[2][1]=1;
    for(int i=3;i<=200;i++) 
       for(int j=0;j<i;j++)
         a[i][j]=(a[i-1][j-1]*(i-j)+a[i-1][j]*(j+1))%Mod;
   while(scanf("%d%d",&n,&m)==2) printf("%d\n",a[n][m]);
    return 0;
}

变态啊 没有注意看多组数据。。。大家注意了 。。

这是一个递推题目....画几个图来讨论情况再来个不完全归纳......

一样得出.. f=f*(j+1)+f*(i-j)

f[n,k]....n是前节车厢 k链的方案数...

见笑了...........

P.S.楼下辛苦了 ........递推大可不必读一次算一次...反正结果是定值........

编译通过...

├ 测试数据 01：答案正确... 525ms

├ 测试数据 02：答案正确... 119ms

├ 测试数据 03：答案正确... 322ms

├ 测试数据 04：答案正确... 150ms

├ 测试数据 05：答案正确... 166ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 88ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 9ms

├ 测试数据 10：答案正确... 353ms

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

Accepted 有效得分：100 有效耗时：1741ms

var n,k,i,j:longint;

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

begin

while not(eof) do

begin

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

readln(n,k);

for i:=0 to n do f:=1;

for i:=1 to n do

for j:=1 to k do

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

writeln(f[n,k]);

end;

end.

简单递推.

可以设f表示从轻到重放到了第i个，用了j个链。然后

f可以由f放一个大的推到而来，但是放的位置不能在原来的j-1链个里面所以第一种情况就是f*((i-1)-(j-1))即所谓的f*(i-j)

注意：这个链必须在放在前面

第二种情况就是加一个链……即f*(j+1)，放在链里面或放在末尾，例：在链ij中放入k 则i k j 且k>i>j 那么消掉一条链且创造了一条链，所以等价……

所以这是个标准的递推……我否定了Andy_Xu 的话……

不过还是要Orz Andy！

while not eof do

begin

readln(n,k);

....

end;

千万别read(n,k)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

program p1584;

var i,j,k,n:longint;

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

begin

f[1,0]:=1;

for i:=1 to 200 do

begin

f:=1;

for j:=1 to i-1 do

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

end;

while not eof do

begin

readln(n,k);

writeln(f[n,k]);

end;

end.

Flag 　　 Accepted

题号 　　P1584

类型(?) 　　其它

通过 　　266人

提交 　　588次

通过率 　　45%

难度 　　1

提交 讨论 题解

倒啊，比赛的时候把动态方程写成了：f[j]:=(f[j]+(j+1)+f[j-1]+(i-j)) mod 2009;

一直在郁闷为什么样例都过不了....

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

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

var n,i,j,k:longint; f:array[0..200]of longint;begin while not(eof) do begin readln(n,k); fillchar(f,sizeof(f),0); f[0]:=1; for i:=1 to n do for j:=k downto 1 do if i>j then begin f[j]:=(f[j]*(j+1)+f[j-1]*(i-j)) mod 2009; end; writeln(f[k]); end;end.

Flag 　　 Accepted

题号 　　P1584

类型(?) 　　其它

通过 　　265人

提交 　　587次

通过率 　　45%

难度 　　1

var

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

n,k,i,j:longint;

begin

while not eof(input) do

begin

readln(n,k);

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

for i:=0 to 200 do f:=1;

for i:=1 to n do

for j:=1 to i-1 do

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

writeln(f[n,k]);

end;

end.

Vivid Puppy Vs Vijos Dragon

Vivid Puppy:

编译通过...

├ 测试数据 01：运行超时|无输出...

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 25ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：运行超时|无输出...

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

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

Unaccepted 有效得分：80 有效耗时：50ms

Vijos Dragon:

编译通过...

├ 测试数据 01：答案正确... 243ms

├ 测试数据 02：答案正确... 9ms

├ 测试数据 03：答案正确... 118ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 118ms

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

Accepted 有效得分：100 有效耗时：547ms

同一个程序 不同的结果

Vivid Puppy快，但没Ac

Vijos Dragon慢，但Ac了

雷死我了

f(n,k)=f(n-1,k-1)*(n-k)+f(n-1,k)*(k+1)

var

n,k,i,j:longint;

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

begin

f[1,0]:=1;

for i:=1 to 200 do

begin

f:=1;

for j:=1 to i-1 do

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

end;

while not(eof) do

begin

readln(n,k);

writeln(f[n,k]);

end;

end.

每次增加一个第i轻的 然后看看放在不同位置分别有多少种方法..

dp[n][k]表示放置了n个之后使用连接链k条的方法总数

现在放入第n + 1个.. 而且这第n + 1个比前n个都重

那么当放在最后面的时候不需要连接链.放在其他地方都需要连接链..

于是就可以推出n + 1的情况 @

如现在有一个1到n的排列.. 需要连接链k条

现在加入一个n+1 那么一共有n+1个位置可以放它.. 其中放在最后一个位置是不需要连接链的 因为n+1最重...

而其他n个位置就相当于是在相邻的a和b之间插入一个n+1

如果a > b 那么本来就需要连接链 插入之后是a, n + 1, b这样只需要一条连接链 保持不变

如果a < b 那么本来不需要连接链 现在需要一条

然后由于1到n的这个排列本来就有k条连接链 所以有k个a > b的情况以及n - 1 - k个a < b的情况

没看到有多组数据，白交了4次……第5次AC。

f[i][j]表示i个数，连接数是j时有多少种。

f[i][j]=(f[j]*(j+1)+f[j-1]*(i-j)%2009;

每个单调上升的序列看成一段。这时一共有j+1段。

前一项表示在所有f[j]的序列的基础上添加一个i，在每段最后都可以添加，所以乘以j+1。

后一项表示在所有f[j-1]的序列的基础上添加一个i，除了每段的最后都可以添加，所以乘以(i-j)。

每次增加一个第i轻的 然后看看放在不同位置分别有多少种方法..

dp[n][k]表示放置了n个之后使用连接链k条的方法总数

现在放入第n + 1个.. 而且这第n + 1个比前n个都重

那么当放在最后面的时候不需要连接链.放在其他地方都需要连接链..

于是就可以推出n + 1的情况 @

如现在有一个1到n的排列.. 需要连接链k条

现在加入一个n+1 那么一共有n+1个位置可以放它.. 其中放在最后一个位置是不需要连接链的 因为n+1最重...

而其他n个位置就相当于是在相邻的a和b之间插入一个n+1

如果a > b 那么本来就需要连接链 插入之后是a, n + 1, b这样只需要一条连接链 保持不变

如果a < b 那么本来不需要连接链 现在需要一条

然后由于1到n的这个排列本来就有k条连接链 所以有k个a > b的情况以及n - 1 - k个a < b的情况

方程懒得写了....

READLN!!

没看到有多组数据，白交了4次……第5次AC。

f[i][j]表示i个数，连接数是j时有多少种。

f[i][j]=(f[j]*(j+1)+f[j-1]*(i-j)%2009;

每个单调上升的序列看成一段。这时一共有j+1段。

前一项表示在所有f[j]的序列的基础上添加一个i，在每段最后都可以添加，所以乘以j+1。

后一项表示在所有f[j-1]的序列的基础上添加一个i，除了每段的最后都可以添加，所以乘以(i-j)。

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35999476_d.html如果想获取更多vijos题解请登陆：http://xujieqi.blog.hexun.com/35722312_d.html

本菜跪求大牛们的精辟讲解，虽然AC了，但不知方程怎样得出？？？

不会，这题有意义吗？

楼下的在搞什么呀。。只要求最大的N和K。其他不就出来啦。。不用每次都DP的吧。。

LX的，同余不会吗？

var i,j,m,n,k,l,p:longint;

f:array[0..250,-1..250] of longint;

begin

while not eof do

begin

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

readln(n,k);

for i:=0 to n do

f:=1;

for i:=2 to n do

for j:=1 to i-1 do

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

writeln(f[n,k] mod 2009)

end

end.

Accepted 有效得分：100 有效耗时：0ms

Puppy反应神猛

第一次WA在以为只有一组数据

其实是简单的一个DP：

状态转移方程：f=f*(j+1)+f*(i-j)；

f表示前i个车厢用j个链相连的总数

比赛时没看见数据有好多组，刚才又出现了程序输出比正确答案长，提交了n次，把read改为readln就过了