排列组合数
概述
排列数:
从n个不同元素，任取个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号(或者是)表示。
组合数:
从n个不同元素中，任取 个元素组成一个集合，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号来表示,组合数也常用表示
各种排列
不相邻的排列
1-n这n个自然数中选k个，这k个中任何两个数都不相邻的组合有
错位排列
我们把错位排列问题具体化，考虑这样一个问题：
n封不同的信，编号分别是1,2,3,4,5，现在要把这五封信放在编号1,2,3,4,5的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法？
假设我们考虑到第n个信封，初始时我们暂时把第n封信放在第n个信封中，然后考虑两种情况的递推：
前面n-1个信封全部装错；
前面n-1个信封有一个没有装错其余全部装错。
对于第一种情况，前面n-1个信封全部装错：因为前面n-1个已经全部装错了，所以第n封只需要与前面任一一个位置交换即可，总共有种情况。
对于第二种情况，前面n-1个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若n-1个信封中如果有一个没装错，那么我们把那个没装错的与n交换，即可得到一个全错位排列情况。
其他情况，我们不可能通过一次操作来把它变成一个长度为 的错排。
于是可得错位排列的递推式为。
错位排列数列的前几项为0,1,2,9,44,265。
圆排列
n个人全部来围成一圈，所有的排列数记为。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。 所以有
部分圆排列公式
三种求组合数的方法
通过预处理
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2005,mod=1e9+7;
int c[N][N];
void init(int n,int m)
{ for(int i=0;i<=n;i++) { for(int j=0;j<=i;j++) { if(j==0) c[i][j]=1; else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } }
}
int main()
{ init(2000,2000); int n,a,b; 20. cin>>n; for(int i=1;i<=n;i++) { cin>>a>>b; cout<<c[a][b]<<endl; } return 0;
}
随取随用，可预处理逆元和阶乘
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=1e9+7;
int fac[N],infac[N];
int qpow(int a,int n,int mod)
{ int ans=1; while(n) { if(n&1) ans=ans*a%mod; a=a*a%mod; n>>=1; } return ans;
}
void init()
{ fac[0]=1; infac[0]=1; for(int i=1;i<N;i++) { fac[i]=fac[i-1]*i%mod; infac[i]=infac[i-1]*qpow(i,mod-2,mod)%mod; }
}
int C(int a,int b)
{ return fac[a]*infac[b]%mod*infac[a-b]%mod;
}
signed main()
{ int n; cin>>n; init(); //for(int i=1;i<=100;i++) cout<<fac[i]<<" "<<infac[i]<<endl; for(int i=1;i<=n;i++) { int a,b; cin>>a>>b; cout<<C(a,b)<<endl; } return 0;
}
Lucas定理，当p为质数时，有
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int qpow(int a,int n,int mod)
{ int ans=1; while(n) { if(n&1) ans=ans*a%mod; a=a*a%mod; n>>=1; } return ans;
}
int C(int a,int b,int p)
{ int res=1; for(int i=1,j=a;i<=b;i++,j--) { res=res*j%p*qpow(i,p-2,p)%p; } return res;
}
int lucas(int a,int b,int p)
{ if(a<b) return 0; if(a<p&&b<p) return C(a,b,p); else return lucas(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
signed main()
{ int n; cin>>n; for(int i=1;i<=n;i++) { int a,b,p; cin>>a>>b>>p; cout<<lucas(a,b,p)<<endl; } return 0;
}
