我的思路是这样的：
枚举正确的个数i，然后从n个位置中选择i个位置，C(n,i)
那么剩下的n-i个位置，都不是答案，我们暂时成为错位排列
现在的难点就在于，，如何球错位排列
设F[i]表示i个数字，错位排列的种类数那么，先只考虑前i-1个数字错位排列，暂时在第i个位置把数字i放上，此时是不合法的因为i第i个位置不能放i，所以要考虑把i和其他数字调换位置在前i-1个位置中，选出一个位置，把这个位置的数字与数字i调换位置，可能的情况就有(i-1)*F[i-1]看似情况全部考虑了，其实还有一种情况没考虑。假如前i-1个位置中，存在一个位置k,放的是数字k，然后另外i-2个数字是错位排列的，那么此时只要把这个数字k和数字i交换，也能使新生成的排列是错位排列这种情况是不属于第一种情况的。这种情况的种类有 枚举k的位置 * i-2个数字错位排列的情况数,即(i-1)*F[i-2]综上所述F[i]=(i-1)*(F[i-1]+F[i-2])其中边界F[1]=0,F[2]=1
那么这题就基本做完了~
#include<map>#include<set>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<string>#include<vector>#include<cstring>#include<iostream>#include<algorithm>#include<functional>using namespace std;typedef long long LL;typedef pair<int, int> PII;const int MX = 28 + 5;LL F[MX];LL C[MX][MX];int main() {F[0] = 1; F[1] = 0; F[2] = 1;for(int i = 3; i < MX; i++) {F[i] = (F[i – 1] + F[i – 2]) * (i – 1);}C[0][0] = 1;for(int i = 1; i < MX; i++) {C[i][0] = C[i][i] = 1;for(int j = 1; j < i; j++) {C[i][j] = C[i – 1][j – 1] + C[i – 1][j];}}int n;while(~scanf("%d", &n), n) {LL ans = 0;for(int i = (n + 1) / 2; i <= n; i++) {ans += C[n][i] * F[n – i];}printf("%I64d\n", ans);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
一直有记日记的习惯，可是，旅行回来，
