首页 > 代码库 > 错排问题
错排问题
什么是错排问题？
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排.
2种计算错排方法
1.递推
有n个元素，考虑放第一个元素为i，放在位置k上。有n-1种方法，再考虑第k个元素，如果放在第i个位置上，，等价于n-2个元素的错排问题，如果不放在第i个位置上，等价于n-1个元素的错排问题，
因此，f[n]=(n-1)*(f[n-1]+f[n-2]);
2.容斥原理
有n个元素，共有n!排列方式.
设集合Ai表示，第i个位置的元素在第i个位置上的全排列数，有(n-1)!。考虑Ai与Aj的交集,等价于去掉第i个位置和第j个位置的全排列数即(n-2)!
同理Ai,Aj,Ak的交集为(n-3)!....依此类推
然后直接容斥原理就行了
参考博客http://blog.csdn.net/acdreamers/article/details/8159679
题目
HDU2048
代码:
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>#include<vector>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define MS(x,y) memset(x,y,sizeof(x))#define MC(x,y) memcpy(x,y,sizeof(x))#define ls o<<1#define rs o<<1|1#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=100100;const int N=1e9;const int mod=1e9+7;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------double mu[25],f[25];int main(){ mu[1]=1; for(int i=2;i<=20;i++) mu[i]=mu[i-1]*double(i); f[1]=0.0;f[2]=1.0; for(int i=3;i<=20;i++) f[i]=(double)(i-1)*(f[i-1]+f[i-2]); //cout<<f[20]<<endl; //cout<<mu[20]<<endl; int c,n; scanf("%d",&c); while(c--){ scanf("%d",&n); printf("%.2lf",f[n]/mu[n]*100.0); printf("%%\n"); }}
HDU2049
#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<map>#include<set>#include<vector>using namespace std;using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define MS(x,y) memset(x,y,sizeof(x))#define MC(x,y) memcpy(x,y,sizeof(x))#define ls o<<1#define rs o<<1|1#define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)typedef pair<int,int> P;const double eps=1e-9;const int maxn=100100;const int N=1e9;const int mod=1e9+7;ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}//-----------------------------------------------------------------------------int T,n,m;ll f[25],d[25];int main(){ f[1]=0;f[2]=1; for(int i=3;i<=20;i++) f[i]=(i-1)*(f[i-1]+f[i-2]); d[1]=1;d[0]=1; for(int i=2;i<=20;i++) d[i]=d[i-1]*i; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); ll tmp=d[n]/(d[m]*d[n-m]); printf("%lld\n",f[m]*tmp); }}
错排问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。