首页 > 代码库 > hdu_5894_hannnnah_j’s Biological Test(打表找规律)
hdu_5894_hannnnah_j’s Biological Test(打表找规律)
题目链接：hdu_5894_hannnnah_j’s Biological Test
题意：
有n个不同的位置围成一个圈，现在要安排m个人坐，每个人至少的间隔为k，问有多少种安排
题解：
先打表找规律，最后发现答案为n*C(n-m*k-1,n-m*k-m)/m
然后这里求组合要预处理一下，逆元也预处理一下
最后还要特判m为1的情况
1 #include<cstdio> 2 typedef long long ll; 3 const int P=1e9+7; 4 5 const int maxn=1e6+3; 6 long long inv[maxn]={0,1},a[maxn],b[maxn]; 7 8 ll pow_mod(ll a, ll b) 9 {10 ll ans = 1;11 while (b)12 {13 if (b & 1)ans = (ans*a) % P;14 b >>= 1, a = (a*a) % P;15 }16 return ans;17 }18 19 ll C(ll x,ll y)20 {21 return b[x]*a[y]%P*a[x-y]%P;22 }23 24 int main(){25 int t;ll n,m,k;26 b[1]=1;27 for(int i=2;i<maxn;i++)b[i]=b[i-1]*i%P;28 for(int i=1;i<maxn;i++)a[i]=pow_mod(b[i],P-2);29 for(int i=2;i<maxn;i++)inv[i]=inv[P%i]*(P-P/i)%P;30 scanf("%d",&t);31 while(t--)32 {33 scanf("%lld%lld%lld",&n,&m,&k);34 ll n0=m*(k+1);35 if(m==1)printf("%lld\n",n);36 else if(n<n0)printf("0\n");37 else printf("%lld\n",(((n*C(n-m*k-1,n-m*k-m))%P)*inv[m])%P);38 }39 }
hdu_5894_hannnnah_j’s Biological Test(打表找规律)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。