题目大意
一个大小为 n的环，选 m 个位置涂黑，要求相邻两个黑点之间至少间隔 k个白点，问方案数。
分析
1. 思路一(较复杂)
令f(n,m)表示n个座位排成一排，选m个，相邻间隔不小于k个方案数。
将这环上n个座位编号从1到n.
①从1开始选的第一个>k :方案数为f(n-k,m)
②从1开始选的第一<=k :方案数为f(n-2k-1,m-1)
剩下问题就转换成求f(n,m)了。我们可以考虑插点法来转化问题，对于m个涂黑的座位，在它们之间（包括两边）m+1个间隔插入n-m个空座位:
x
1
+
x
2
+
.
.
.
+
x
m
+
1
=
n
−
m
(
x
1
>
=
0
,
x
2
>
=
k
.
.
.
x
m
>
=
k
,
x
m
+
1
>
=
0
)
=>
x
1
+
x
2
+
.
.
.
+
x
m
+
1
=
n
−
m
+
2
k
(
x
i
>
=
k
)
我们还可以通过引入一个松弛变量y来使得xi>=1（因为这是我们熟悉的模型）y=(k-1)*(m+1);
x
1
+
x
2
+
.
.
.
+
x
m
+
1
=
n
−
m
+
2
k
−
y
(
x
i
>
=
1
)
再用插板法，n-m+2k-y个球分成m+1堆每堆至少一个有多少种分法。这个答案就是
C
m
n
−
m
+
2
k
−
y
−
1
=
C
m
n
+
k
−
k
∗
m
得到
f
(
n
,
m
)
=
C
m
n
−
k
∗
m
+
k
=>f(n-k,m)=
C
m
n
−
k
∗
m
=>f(n-2k-1,m-1)=
C
m
−
1
n
−
k
∗
m
−
1
A
n
s
=
C
m
n
−
k
∗
m
+
k
∗
C
m
−
1
n
−
k
∗
m
−
1
=
n
∗
C
m
−
1
n
−
k
∗
m
−
1
m
然后用乘法逆元解决除法取模的问题。
1. 思路二
（
引用别人的分析
）首先确定第一个人的位置，第一个人可以从n个椅子中任选一个，然后剩余n-1个椅子。因为人的间隔至少k个椅子，所以从这些符合要求的间隔距离的椅子抽出k*m个，然后剩下的m-1个人就可以随便从剩下的椅子人选了。可以想象成每个人和k个座位绑在一起，一旦这个人有了座位，他后面自动添加这k个座位。
那么第一个人从n个座位中选择一个，并且抽走了k*m个，那么剩下n-1-k*m个座位，在这之中选m-1个作为给其余人座，总数为
s
u
m
=
n
∗
C
m
−
1
n
−
k
∗
m
−
1
，因为这里的人是无差别的。比如有3个人,假设他们坐的位置是(2,4,7),那么,(4,2,7),(7,2,4)是重复计算的，所有sum/m。
总结
第一种思路是不断的将问题转化为我们熟悉的问题，先是想办法把环拆成链，然后在链上将至少间隔k个的问题转化成至少间隔1的问题。
第二种思路可以看作是先将某一个人（就是分析里的第一个人）看作是独特的。由于有m个人，所以结果sum/m。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1000000007;
LL qmod(LL x,int n)//快速幂取模
{
LL ans=1;
for(;n;n>>=1)
{
if(n&1)ans=(ans*x)%mod;
x=x*x%mod;
}
return ans;
}
LL C(int n,int m)//组合数取模
{
if(m>n)return 0;
LL ans=1;
for(int i=1;i<=m;i++)
{
ans=ans*((n-m+i)*qmod(i,mod-2)%mod)%mod;
}
return ans;
}
int main()
{
int T;
LL n,m,k;
scanf("%d",&T);
LL ans;
while(T--)
{
ans=0;
scanf("%lld%lld%lld",&n,&m,&k);
if(m==1)printf("%lld\n",n);
else printf("%lld\n",(C(n-k*m-1,m-1)*n%mod)*qmod(m,mod-2)%mod);
}
return 0;
}
扩展
关于组合取模和乘法逆元问题请参考：
欧几里得算法、扩展欧几里得、乘法逆元
组合取模问题与Lucas定理