本文主要是介绍错排问题【Ybtoj】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
D e s c r i p t i o n Description Description
求多少个 n n n个数的排列 A A A ，满足对于任意的 i ( 1 ⩽ i ⩽ n ) i(1\leqslant i \leqslant n) i(1⩽i⩽n), A i ≠ i A_i \not= i Ai=i
I n p u t Input Input
一个整数 n n n。
O u t p u t Output Output
一个整数，表示答案。
S a m p l e Sample Sample I n p u t Input Input
2
S a m p l e Sample Sample O u t p u t Output Output
1
H i n t Hint Hint
对于 100 % 100\% 100%的数据， 1 ⩽ n ⩽ 20 1\leqslant n \leqslant 20 1⩽n⩽20。
T r a i n Train Train o f of of T h o u g h t Thought Thought
设 F n F_n Fn为方案数
第一步，考虑第 n n n个元素，把它放在某一个位置，比如位置 k k k，一共有 n − 1 n-1 n−1种放法；
第二步，考虑第 k k k个元素，这时有两种情况：
（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有 F n − 2 F_{n - 2} Fn−2种放法；
（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有 F n − 1 F_{n-1} Fn−1种放法。
我用了高精压位
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define Mod 10000
using namespace std;const int t = 25;ll n, A[t][t + 10];void Mul(ll k)
{int g = 0;for(int i = 1; i <= t; ++i){A[k][i] = A[k][i] * (k - 1) + g;g = A[k][i] / Mod;A[k][i] %= Mod;}
}void Add(ll k)
{int g = 0;for(int i = 1; i <= t; ++i){A[k][i] = A[k - 1][i] + A[k - 2][i] + g;g = A[k][i] / Mod;A[k][i] %= Mod;}
}int main()
{scanf("%lld", &n);A[1][1] = 0, A[2][1] = 1;for(int i = 3; i <= n; ++i)Add((ll)i), Mul((ll)i);int l = t + 5;while(l && !A[n][l])l--;printf("%d", A[n][l--]);while(l > 0){if(A[n][l] == 0)printf("0000");else if(A[n][l] < 10)printf("000");else if(A[n][l] < 100)printf("00");else if(A[n][l] < 1000)printf("0");printf("%d", A[n][l--]);}return 0;
}
这篇关于错排问题【Ybtoj】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
