——前提提要：做排列组合题目的时候，要注意long long的问题！！！！题目一：有n封信，每封信都装错了对应的袋子里，问一共有几种“错误”形式？多组数据1<=n<=20例：2 3 输出：1 2题解：本题为简单错排题。直接套公式即可【注意要开long long，否则会爆】。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> typedef long long ll; using namespace std; int f[22],n; ll fun(int n){ if(n==1)return 0; if(n==2)return 1; return (ll)(n-1)*(fun(n-1)+fun(n-2)); } int main(){ while(scanf("%d",&n)!=EOF) printf("%lld\n",fun(n)); return 0; }
题目二:有n个数，顺次排列a[i]=i;问字典序第m个排列是什么？多组数据，1<=N<=1000, 1<=M<=10000例：6 4 输出：1 2 3 5 6 4 11 8 1 2 3 4 5 6 7 9 8 11 10题解：本题目运用next_permutation(a+1, a+1+n);这个函数。所以代码如下：
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> typedef long long ll; using namespace std; int f[22],n; ll fun(int n){ if(n==1)return 0; if(n==2)return 1; return (ll)(n-1)*(fun(n-1)+fun(n-2)); } int main(){ while(scanf("%d",&n)!=EOF) printf("%lld\n",fun(n)); return 0; }
题目三：结婚典礼上，有n对新婚夫妇。玩一个新郎找新娘的游戏，有m个新郎找错了，一共有多少种可能？t组数据，1<=m<=n<=20;例：2 输出：12 2 33 2题解：错排+组合题。组合(杨辉三角)，错排（）因为有m个新郎选错了新娘，所以有n-m个新郎选对了新娘，所以可套用杨辉三角公式得到[函数见下面程序] sun(n,n-m)，错排就不用说了，fun(m);根据乘法原理，选对的方法*选错的方法=最终选的可能数√
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> typedef long long ll; using namespace std; int n,m,t; ll fun(int n){//错排 if(n==1)return 0; if(n==2)return 1; return (ll)(n-1)*(fun(n-1)+fun(n-2)); } ll sun(int x,int y){//组合 if(y==0 || y==x) return (ll)1; return sun(x-1,y)+sun(x-1,y-1); } int main(){ //freopen("e.in","r",stdin); //freopen("e.out","w",stdout); scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); ll a1=fun(m); ll a2=sun(n,n-m); cout<<a1*a2<<endl; } return 0; }
转载于:https://www.cnblogs.com/wuhu-JJJ/p/11161270.html
相关资源：c 排列组合算法，代码简单