问题 D: 记一次惨痛的教训（组合数的计算）

本文主要是介绍问题 D: 记一次惨痛的教训（组合数的计算），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

传说中很多大牛喜欢用自己姓名拼音的重排列，比如著名的吕凯风大牛，他的姓名拼音是lvkaifeng，重新排列之后就得到了VFleaKing，也就是著名的伏特跳蚤国王。现在，火星人觉得VFleaKing太强啦！于是他们也要这样取他们的ID名，现在问题来了，他们的名字都非常长，而且都是由火星文组成的（火星文有好多好多字符）。火星人想请你帮他们算算如果把他们的名字重排有几种方案，当然了，原序列也是一种方案啦_{如果你不帮他们算出正确的答案你就会死哦}

形式化描述：给定一个长度为N的整数序列A1…N，求有多少种不同长度为的N的整数序列B1…N是A的重排，即可重集{Ai}={Bi}。两个序列不同当且仅当它们任一位置上的元素不相等。

输入

第1行：两个正整数N,k，其中N代表该火星人名字的长度，k代表火星文有多少种字符，我们不妨设在有k种字符的情况下的火星文中的字符分别是0到k−1。
第2行：用空格隔开的N个正整数，代表这个火星人的名字，我们保证这N个数字一定在0到k−1的范围内。

输出

第1行：一个正整数——这个火星人的名字重排方案数对109+7取模的结果（火星人的逻辑特别奇怪，只要知道模数是多少就可以放过你了）。

样例输入
复制样例数据 4 2
0 0 1 1

样例输出
6

提示

满足条件的重排共有如下6种：
0,0,1,1
0,1,0,1
1,0,0,1
0,1,1,0
1,0,1,0
1,1,0,0

被自己坑了：10⁹ +7是1e9+7而不是10e9+7，比赛时卡了一个半小时，一直wa，赛后补题又花了快2个小时才补起来，惨痛的教训；还有使用map超时也是一个注意点map的操作是O(logn)的复杂度

思路：设数0到k-1分别有a1，a2，…，ak个，由题目可以推出来ans=C(n,a1)*C(n-a1,a2) * … *C(n-a1-a2-…-an-1,an);
重点是组合数的计算：
1）可以直接利用组合数的公式C(n,m)=n! /((n-m)!m!),因为要%mod，所以要求(n-m)!和m!的逆元，直接利用线性的算法求阶乘的逆元即可，n!直接O(n)求即可；

2）或者直接使用卢卡斯定理也可以

代码1：

const long long  mod=1e9+7;
int len=0;
typedef long long ll;
ll fac[2000005];
ll inv[2100000]={0};
ll cnt[2000005];
template <typename _tp> inline _tp read(_tp&x){char ch=getchar(),sgn=0;x=0;while(ch^'-'&&!isdigit(ch))ch=getchar();if(ch=='-')ch=getchar(),sgn=1;while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(sgn)x=-x;return x;
}ll qmod(ll a,ll b)
{ll sum=1;while(b){if(b&1) sum=sum*a%mod;a=a*a%mod;b>>=1;}sum%=mod;return sum;
}void getinv(long long n)
{fac[0]=1;///求阶乘的最大值for(register int i=1;i<=n;i++)  fac[i]=fac[i-1]*i%mod;///求阶乘最大值的逆元inv[n]=qmod(fac[n],mod-2);for(register int i=n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}inline ll C(ll m,ll n)
{ll ans=1;ans=fac[m]*inv[n]%mod*inv[m-n]%mod;//cout<<fac[m]<<' '<<inv[n]<<' '<<inv[m-n]<<endl;if(ans==0) return 1;return ans;
}int main()
{getinv(2000005);ll n,k;cin>>n>>k;for(register int i=1;i<=n;i++){ll a;read(a);cnt[a]++;}//cout<<Lucas(2,3,4);ll ans=1;ll Cnt=n;for(int i=1;i<=n;i++){ans=ans%mod*C(Cnt,cnt[i])%mod;Cnt-=cnt[i];}ans%=mod;cout<<ans<<endl;}

代码2（卢卡斯定理）

const long long  mod=1e9+7;
long long  cnt[2000005],fac[2000005];
int len=0;
typedef long long ll;
void ini(int n)
{fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i]*i%mod;
}ll exgcd(ll a,ll b,ll& x,ll& y){if(a%b==0){x=0,y=1;return b;}ll r,tx,ty;r=exgcd(b,a%b,y,x);y-=a/b*x;
}ll comp(ll a,ll b,ll m){if(a<b) return 0;if(a==b) return 1;if(b>a-b) b=a-b;ll ans=1,ca=1,cb=1;ca=fac[a];cb=fac[b]*fac[a-b]%m;ll x,y;exgcd(cb,m,x,y);x=(x%m+m)%m;ans=ca*x%m;return ans;
}ll lucas(ll a,ll b,ll m){ll ans=1;while(a&&b){ans=(ans*comp(a%m,b%m,m))%m;a/=m;b/=m;}return ans;
}int main()
{ini(2000002);map<int ,int >m;ll n,k;cin>>n>>k;for(int i=1;i<=n;i++){int a;scanf("%d",&a);cnt[a]++;}ll ans=1;ll Cnt=n;for(int i=1;i<=n;i++){ans=ans%mod*lucas(Cnt,cnt[i],mod);Cnt-=cnt[i];}ans%=mod;cout<<ans<<endl;
}