| 题目名称 | 616. 整理牙刷 |
|---|---|
| 输入输出 | put.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2011-11-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：60， 提交：110， 通过率：54.55% | ||||
 Я люблю тебя |
100 | 0.000 s | 0.00 MiB | C++ |
 卢本伟 |
100 | 0.000 s | 0.00 MiB | C++ |
 FoolMike |
100 | 0.002 s | 0.49 MiB | Pascal |
 柯哀王道 |
100 | 0.003 s | 0.29 MiB | C++ |
 郭垚池 |
100 | 0.003 s | 0.55 MiB | Pascal |
 /k |
100 | 0.003 s | 0.67 MiB | C++ |
 _stranger |
100 | 0.003 s | 0.70 MiB | C++ |
 lizhe |
100 | 0.004 s | 0.12 MiB | Pascal |
 Czb。 |
100 | 0.004 s | 0.26 MiB | C++ |
 kaaala |
100 | 0.004 s | 0.27 MiB | C++ |
| 本题关联比赛 | |||
| 20111110 | |||
| 20111110 | |||
| 关于 整理牙刷 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
简单地想，假设已知f（n-1) (n-1支牙刷的错排方案），那么对于其中任意一种方案，将其中n-1个元素任意一个与第n个交换，可得（n-1)f(n-1)种方案；
假设已知f(n-2),则n-1支牙刷必有一支（可以是任意一只）放在了原位置上，将其与第n支交换即可。共（n-1）f(n-1)种方案。 易知对f(n-3).....(f(1)不存在使f（n）成立的方案。 故f(n)=(n-1)(f(n-1)+f(n-2). | ||||
|
啊，我看题解了= =............我是菜B，自己推不出来....
 raywzy
2013-10-01 19:57
3楼
| ||||
 Makazeu
2012-11-08 10:56
2楼
| ||||
|
数值递推，
（推公式当中就会发现发现， 递推式明显和“全排列”的公式有关。） | ||||
gungnir
Truth.Cirno【问题描述】
众所周知，XW同学早晨起来是要刷牙的。
XW同学有 N 支牙刷，又有 N 个牙刷套 , 开始的时候，一支牙刷对应放在一个牙刷套中。可是有一天，XW同学把所有牙刷套里的牙刷都拿出来，玩了一会儿，他又要把所有的牙刷都放回去。可是，他忽然一想，我可不可以使得没有任何一支牙刷放回它原来的牙刷套里面呢 ?
XW同学努力试了很久，却一直没有成功过一次。于是他断定这个要求是无法达成的，你怎么认为的呢 ?
【输入文件】
输入文件 put.in 只包括一个整数 N ，表示牙刷和牙刷套的总数。
【输出文件】
输出文件 put.out ，如果存在满足要求的方法，输出放法方案总数 L 。因为方案总数可能比较大，所以你可以将答案 Mod 1206 后再输出。如果不存在满足要求的方法，则输出 "No Solution!”
【样例输入】
3
【样例输出】
2
【数据范围】
对于 40 ％的数据，保证 N ≤ 9
对于 100 ％的数据，保证 N ≤ 100000