放牙刷 (put.pas/c/cpp)

【问题描述】

    众所周知，黄黄同学早晨起来是要刷牙的。

    黄黄同学有N支牙刷，又有N个牙刷套,开始的时候，一支牙刷对应放在一个牙刷套中。可是有一天，黄黄同学把所有牙刷套里的牙刷都拿出来，玩了一会儿，他又要把所有的牙刷都放回去。可是，他忽然一想，我可不可以使得没有任何一支牙刷放回它原来的牙刷套里面呢?

    黄黄同学努力试了很久，却一直没有成功过一次。于是他断定这个要求是无法达成的，你怎么认为的呢?

【输入文件】

    输入文件put.in只包括一个整数N，表示牙刷和牙刷套的总数。

【输出文件】

    输出文件put.out，如果存在满足要求的方法，输出放法方案总数L。因为方案总数可能比较大，所以你可以将答案Mod 1206后再输出。如果不存在满足要求的方法，则输出"No Solution!”

【样例输入】

    3

【样例输出】

    2

【数据范围】

    对于40％的数据，保证N≤9

    对于100％的数据，保证N≤100000

    【时限】

    ls

很容易看出它就是错位排列，用通项公式明显不适用，应使用递推式

Ｆ［Ｉ］＝（Ｉ-１）*（Ｆ［Ｉ－１］+Ｆ［Ｉ－２］）

证明：*　　*　*　　*　*　　*....

　　　１　２　３　４　５　６....

假设现在Ｉ＝６，第６位上有５种选择（Ｉ－１），比如在第６位上放的是３，如果第３位上又被６占据，那么剩下的４位自行错位排列有Ｆ［４］种方案（Ｆ［Ｉ－２］），可以把这种情况视为３＼６原先各在其位，其余４位错位，而后３/６互换

如果如果没有出现３＼６相互占据的情况，说明３不在第３位上，３＼６互换前，前５位已错位排序讫，那么就有Ｆ［５］种情况，互换后依然满足错位，方案数也是Ｆ［Ｉ－１］

所以Ｆ［Ｉ］＝（Ｉ－１）*（Ｆ［Ｉ－１］+Ｆ［Ｉ-２］）

边界Ｆ［２］＝１　Ｆ［３］＝２

Ｎ＝０或Ｎ＝１无解

program fgdfdfd;
var n,i,j:longint;
    f:array[1..100000]of longint;
begin
assign(input,'put.in');assign(output,'put.out') ;
reset(input); rewrite(output);
fillchar(f,sizeof(f),0);
f[2]:=1 ; f[3]:=2;
readln(n);
if n in [0..1] then writeln('No Solution!')
else
begin
for i:=4 to n do
f[i]:=((i-1)*(f[i-1] +f[i-2] )) mod 1206;
writeln(f[n]) ;
end;
close(input); close(output);
end.