概念
先上唯一看得懂的错排概念，大概像递推dp一样？分情况分步骤往上级递推出的公式，具体过程如下：
新郎官题目大意：
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
思路：也算是一种错排的扩展，但是得用到排列组合的公式，从n对新婚夫妇里选m个新郎。
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int n,m,i,j,t; cin>>t; while(t--){ cin>>n>>m; int dp[25]; dp[1]=0; dp[2]=1; for(i=3;i<=n;i++) dp[i]=(i-1)*(dp[i-1]+dp[i-2]); int mo=1,zi=1,z2=1,z3=1; for(i=1;i<=n;i++) mo*=i; for(i=1;i<=(n-m);i++) z2*=i; for(i=1;i<=m;i++) z3*=i; cout<<(dp[m])*((mo)/(z2*z3))<<endl; } }
老天爷签名大意：
首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字
求都不中奖的概率。
思路：首先列出所有的可能，然后再除以都不中奖的可能，都不中奖也就是错排的方案数.
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int n,i,j,t,dp[25]; dp[0]=0,dp[1]=0,dp[2]=1; for(i=3;i<=20;i++){ dp[i]=(i-1)*(dp[i-1]+dp[i-2]); } int sum[25]; sum[0]=0,sum[1]=1,sum[2]=2; for(i=3;i<=20;i++){ sum[i]=i*sum[i-1]; } cin>>t; while(t--){ cin>>n; double ans1; ans1=dp[n]*1.0/sum[n]; ceil(ans1); ans1*=100; //cout<<dp[n]<<" " <<sum[n]<<endl; printf("%.2lf%%\n",ans1); } }
