组合数学-HDU5894

81 阅读 0 评论 54 点赞

我是靠谱客的博主高兴心锁，最近开发中收集的这篇文章主要介绍组合数学-HDU5894，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://vjudge.net/contest/183475#problem/C

题目大意：

圆周上有N个不同的椅子，要让M个相同的人坐在上面，使得两人之间至少隔K把空椅子，求方案数（模1e9+7）。

0< M < N<1e6, 0< K<1000.

题解：

考虑每两个人之间隔了几把椅子。可以发现，一共有M个数，和为N-M，且每个数都>=K.将每个数都减去K-1，即得到：M个正数之和为N-K*M，方案数为C(N-K*M-1,M-1).需要乘以圆排列的N，同时每个方案被算了M次，再除以M。

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

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

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

答案为：C(N-K*M-1,M-1)*N/M。需要用预处理阶乘的方法计算组合数。注意特判M=1的情况。

#include<bits/stdc++.h>
#define ll long long
const ll mod=1e9+7;
using namespace std;
ll qmod(ll n,ll m,ll mod)
{
ll ans=1;
while(m)
{
if(m&1)ans=(ans*n)%mod;
m>>=1;
n=(n*n)%mod;
}
return ans;
}
ll C(ll n,ll m)
{
if(n<m||n<0||m<0)
return 0;
ll ans=1;
for(int i=1;i<=m;i++)
ans=(ans*(n-i+1)%mod)*qmod(i,mod-2,mod)%mod;
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
if(m==1)
{
printf("%dn",n);
continue;
}
ll ans=C(n-m*k-1,m-1);
ans=(ans*n%mod)*qmod(m,mod-2,mod)%mod;
printf("%I64dn",ans);
}
}

对阶乘和阶乘逆元打表，用时更短

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <stack>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;
#define showtime fprintf(stderr,"time = %.15fn",clock() / (double)CLOCKS_PER_SEC)

#define lld %I64d

#define REP(i,k,n) for(int i=k;i<n;i++)

#define REPP(i,k,n) for(int i=k;i<=n;i++)

#define scan(d) scanf("%d",&d)

#define scanl(d) scanf("%I64d",&d)

#define scann(n,m) scanf("%d%d",&n,&m)

#define scannl(n,m) scanf("%I64d%I64d",&n,&m)

#define mst(a,k)
memset(a,k,sizeof(a))

#define LL long long

#define N 1000005

#define mod 1000000007

inline int read(){int s=0;char ch=getchar();for(; ch<'0'||ch>'9'; ch=getchar());for(; ch>='0'&&ch<='9'; ch=getchar())s=s*10+ch-'0';return s;}
LL f[N], f2[N], inv[N];
void init()
{
f[0] = f[1] = f2[0] = f2[1] = inv[0] = inv[1] = 1;
for (int i = 2; i < N; i++)
{
f[i] = f[i - 1] * i % mod;
//阶乘打表
inv[i] = inv[mod % i] * (mod - mod / i) % mod;
//求逆元
f2[i] = f2[i - 1] * inv[i] % mod;
//阶乘逆元打表
}
}
inline LL C (int n, int m) {
if (m < 0 || n < m) return 0;
return f[n] * f2[m] % mod * f2[n - m] % mod;
}
int main()
{
init();
int t;
scan(t);
while(t--)
{
int n,m,k;
scann(n,m);scan(k);
if(m==1)
{
printf("%dn",n);
continue;
}
LL ans = C(n-1-m*k,m-1) * inv[m] % mod * n % mod;
printf("%lldn",ans);
}
return 0;
}