错排问题【Ybtoj】

本文主要是介绍错排问题【Ybtoj】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$Description$

求多少个$n$个数的排列$A$ ，满足对于任意的$i(1⩽i⩽n)$,$A_i\ne i$

$Input$

一个整数$n$。

$Output$

一个整数，表示答案。

$Sample$ $Input$

2

$Sample$ $Output$

1

$Hint$

对于$100\%$的数据，$1⩽n⩽20$。

$Train$ $of$ $Thought$

设$F_n$为方案数
第一步，考虑第$n$个元素，把它放在某一个位置，比如位置$k$，一共有$n-1$种放法；
第二步，考虑第$k$个元素，这时有两种情况：
（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有$F_{n-2}$种放法；
（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有$F_{n-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】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---