整理牙刷 (jdoj-2433)
题目大意：n个牙刷放进n个牙刷套里，每一个牙刷对应一个唯一的牙刷套。最后求每个牙刷都不在对应牙刷套里的方案数，结果mod 1206。
注释：n<=$10^6$。
想法：这题显然，直接推导是很吓人的是吧，所以我们想到将此题分解，通过递推处理。这题如果硬递推.....好像不太好办。我们已经介绍过了处理递推的利器——分划（分划？猛戳看黄字）。递推的精髓是什么？就是我的已知比较庞大——我们知道前（i-1）个的答案，我们用a[]来记录方案数。那么，我们思考，如何处理才能解决呢？将答案分划：我们将牙刷标记为$A_1,A_2... ...A_i$，将牙刷套标记为$a_1,a_2... ...a_i$。下标相等即为对应。分化就是考虑$A_1$的位置——有i-1中选择，而此时，不难发现——我们已经死了....所以，想到处理分划的强力手段——二次分划。我们如果考虑，对于$A_1$的每一个位置j，我们可以枚举$A_j$的位置，分两种：
1.在$a_1$上。此时，我们可以发现，剩下的i-2种必须满足条件，此时，f [ i ] += f [ i - 1 ] 。
2.不在$a_1$。此时，我们发现：除了$A_1$外，其他的每一个牙刷都有一个对应的牙刷套，其中，$A_j$对应$a_1$，剩下的按下标对应，所以，除了$A_1$外的数也必须满足条件。此时，f [ i ] += f [ i - 2 ]。
此时，$A_1$有i-1种选取的方式。所以，此时，f [ i ] = ( i - 1 ) * ( f [ i - 1 ] + f [ i - 2 ] ) 。另外，介绍一下——这样的排列我们称之为“错位排列”。
最后，附上丑陋的代码......
1 #include <iostream> 2 #include <cstdio> 3 #define mod 1206 4 using namespace std; 5 int f[100010]; 6 int main() 7 { 8 int n; 9 scanf("%d",&n); 10 f[1]=0; 11 f[2]=1; 12 for(int i=3;i<=n;i++) 13 { 14 f[i]=(i-1)%mod*(f[i-1]%mod+f[i-2]%mod)%mod; 15 } 16 if(n==1||n==0) 17 { 18 printf("No Solution!"); 19 return 0; 20 } 21 printf("%d",f[n]%mod); 22 return 0; 23 }
错误：别忘记n==0是也是No Solution！。
未经博主允许严禁转载。