首页 > 代码库 > HDU 5894 hannnnah_j’s Biological Test (组合数学) -2016 ICPC沈阳赛区网络赛
HDU 5894 hannnnah_j’s Biological Test (组合数学) -2016 ICPC沈阳赛区网络赛
题目链接
题意:一个大小为 nn
的环,选 mm
个位置涂黑,要求相邻两个黑点之间至少间隔 kk
个白点,问方案数。
题解:考虑从 0 开始的标号最小的涂黑的位置,有两种情况:
如果该位置 \geq k≥k
,相当于在一排(不是环) n - kn−k
个椅子里面放 mm
个人;
如果该位置 < k<k
, 相当于在一排 n - 2k - 1n−2k−1
个椅子里面放 (m - 1)(m−1)
个人。这种情况有 k 种。
最后考虑在一排 nn
个椅子里面放 mm
个人的方案数,相当于要找 (m + 1)(m+1)
个变量满足 x_1 \geq 0, x_{2, 3, \ldots, m} \geq k + 1, x_{m + 1} \geq 1x?1??≥0,x?2,3,…,m??≥k+1,x?m+1??≥1
同时 x_1 + x_2 + \cdots + x_{m + 1} = nx?1??+x?2??+?+x?m+1??=n
的方案数。这个方案数就是 \binom{n - (m - 1)k}{m}(?m?n−(m−1)k??)
.
至于为什么是上述式子,其中 x_1x?1??
表示的是 11
的下标,x_{2, 3, \ldots, m}x?2,3,…,m??
表示的是每个人离前一个人的距离,最后的 x_{m + 1}x?m+1??
是松弛变量。可以加加减减让大家的限制都变成 \geq 1≥1
,就是熟悉的模型啦。
#include <map>#include <queue>#include <math.h>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <algorithm>#include <iostream>using namespace std;long long a[1000005];const long long mod=1000000007;long long quick(long long a,long long b){ long long ans=1; while(b) { if(b&1) { ans=ans*a%mod; b--; } b>>=1; a=a*a%mod; } return ans;}int main(){ int T; long long i,n,m,k; a[1]=1; for(i=2; i<=1000000; i++) a[i]=(a[i-1]*i)%mod; scanf("%d",&T); while(T--) { scanf("%lld%lld%lld",&n,&m,&k); if(m==1) printf("%lld\n",n); else if(m+m*k>n) printf("0\n"); else if(m+m*k==n) printf("%lld\n",k+1); else { long long y=m-1; long long x=n-m*k-1; long long ans=a[x]*quick(a[x-y],mod-2)%mod*quick(a[y],mod-2)%mod; printf("%lld\n",n*ans%mod*quick(m,mod-2)%mod); } } return 0;}
HDU 5894 hannnnah_j’s Biological Test (组合数学) -2016 ICPC沈阳赛区网络赛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。