HDU5894分位置（组合数，lucas，乘法逆元）

96 阅读 0 评论 64 点赞

我是靠谱客的博主能干饼干，这篇文章主要介绍HDU5894分位置（组合数，lucas，乘法逆元），现在分享给大家，希望可以做个参考。

题意：

现在 m个考生人需要坐在有n个座位的圆桌上。你需要安排位置，使得任意两个考生之间相距至少k个位置。桌子有编号，考生a和b交换位置视作一种方案，问有多少方案，mod 1e9+7。(0 < m < n < 1e6, 0 < k < 1000)

组合数取模，mod为素数的收，当n，m比较大的时候用到lucas定理去求。

分析转自点击打开链接

假定一个人已经坐在了某个位置,如图所示

那还剩下n-1个位置,而要求相邻两人之间必须隔k个位置,所以m个人就有m*k个位置不能坐

那剩下的位置数为n-1-m*k,由于一个人已经坐好,那我需要从这些剩下的位置中挑选出m-1个位置供剩下的m-1个人就坐

故组合数为C(n-m*k-1,m-1)

然后因为有n个位置,所以第一个人位置的选法就有n种

再考虑此题中每个人都是一样的,即不同方案仅仅是坐的位置序列不同,那上述做法会重复计算m次

比如有3个人,假设他们坐的位置是(2,4,7),那么,(4,2,7),(7,2,4)是重复计算的

故方案数的最终式子应为[C(n-m*k-1,m-1)*n/m]%1000000007

那求解组合数不用想肯定得用lucas定理,毕竟n和m有点大,直接打表已经存不下结果,且会超时

而除法取模部分,考虑到1000000007是质数,且m<1000000007,所以gcd(m,1000000007)=1,故可以直接采取乘法逆元

除法取模就要转化为乘上乘法逆元来做了

乘法逆元：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//扩展欧几里得
void ext_gcd(ll a, ll b, ll&d , ll& x, ll& y){
if(!b) {d = a; x = 1; y = 0;}
else{
ext_gcd(b,a%b,d,y,x);
y -= x * (a/b);
}
}
//计算模n下a的逆，如果不存在逆，则返回-1
ll inv(ll a,ll n){
ll d,x,y;
ext_gcd(a,n,d,x,y);
return d == 1?(x+n) % n: -1;
}

求乘法逆元另一个方法是利用欧拉定理。

如果mod为素数，a的逆为pow_mod(a,mod-2,mod).

复制代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 1000005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
typedef long long ll;
ll fac[N];
void init(){
    fac[0] = 1;
    for(int i=1;i<=N;i++){
        fac[i] = i * fac[i-1] % mod;
    }
}
ll pow_mod(ll a,ll b){
    ll res = 1;
    a = a %mod;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a*a % mod;
        b >>= 1;
    }
    return res;
}
ll C(ll n, ll m){
    if(m>n)
        return 0;
    return  fac[n]*pow_mod(fac[m]*fac[n-m]%mod,mod-2)%mod;
}
ll Lucas(ll n,ll m)
{
    if(m==0)
        return 1;
    return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
//扩展欧几里得
void ext_gcd(ll a, ll b, ll&d , ll& x, ll& y){
    if(!b) {d = a; x = 1; y = 0;}
    else{
        ext_gcd(b,a%b,d,y,x);
        y -= x * (a/b);
    }
}
//计算模n下a的逆，如果不存在逆，则返回-1
ll inv(ll a,ll n){
    ll d,x,y;
    ext_gcd(a,n,d,x,y);
    return d == 1?(x+n) % n: -1;
}
int main(){
    int T;
    init();
    scanf("%d",&T);
    while(T--){
        ll n,m,k;
        scanf("%lld%lld%lld",&n,&m,&k);
        printf("%lldn",(Lucas(n-1-m*k,m-1)*n%mod)*inv(m,mod)%mod);
       // printf("%lldn",(Lucas(n-1-m*k,m-1)*n%mod)*pow_mod(m,mod-2)%mod);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 1000005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
typedef long long ll;
ll fac[N];
void init(){
    fac[0] = 1;
    for(int i=1;i<=N;i++){
        fac[i] = i * fac[i-1] % mod;
    }
}
ll pow_mod(ll a,ll b){
    ll res = 1;
    a = a %mod;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a*a % mod;
        b >>= 1;
    }
    return res;
}
ll C(ll n, ll m){
    if(m>n)
        return 0;
    return  fac[n]*pow_mod(fac[m]*fac[n-m]%mod,mod-2)%mod;
}
ll Lucas(ll n,ll m)
{
    if(m==0)
        return 1;
    return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
//扩展欧几里得
void ext_gcd(ll a, ll b, ll&d , ll& x, ll& y){
    if(!b) {d = a; x = 1; y = 0;}
    else{
        ext_gcd(b,a%b,d,y,x);
        y -= x * (a/b);
    }
}
//计算模n下a的逆，如果不存在逆，则返回-1
ll inv(ll a,ll n){
    ll d,x,y;
    ext_gcd(a,n,d,x,y);
    return d == 1?(x+n) % n: -1;
}
int main(){
    int T;
    init();
    scanf("%d",&T);
    while(T--){
        ll n,m,k;
        scanf("%lld%lld%lld",&n,&m,&k);
        printf("%lldn",(Lucas(n-1-m*k,m-1)*n%mod)*inv(m,mod)%mod);
       // printf("%lldn",(Lucas(n-1-m*k,m-1)*n%mod)*pow_mod(m,mod-2)%mod);
    }
}