参考loj2265中关于杨表的相关知识
先来考虑$m\mid n$的情况：
记$t=\frac{n}{m}$，将序列划分为$[1,m],[m+1,2m],...,[(t-1)m+1,tm]$这$t$段，每一段都至少有$k$个物品且可以同时取到，因此取到最小值时必然都恰为$k$个
构造一个$t$列且每列有$k$个格子的杨表，其中第$i$列记录第$t-i+1$段中的$k$个物品相对于该段左端点的距离，不难发现此时合法即要求其为半标准杨表，也即求$g_{m,\{t,t,...,t\}}$（共$k$个$t$）
根据性质3.3，即有$g_{m,\{t,t,...,t\}}=\prod_{i=1}^{k}\prod_{j=1}^{t}\frac{m+j-i}{(k-i)+(t-j)+1}$
先枚举$i$，并分别考虑后者的分子和分母，不难发现即$\frac{(m-i+t)!(k-i)!}{(m-i)!(k-i+t)!}$
将上下同时约掉一个$t!$，即可预处理阶乘及逆元并$o(m\log P)$计算该式
再来考虑$m\not\mid n$的情况：
令$t=\lfloor\frac{n}{m}\rfloor,p=n\ mod\ m$，对其分类讨论：
1.若$p\le m-k$，即需要保证$t$段中每一段的前$p$个位置不能放物品（否则不难得到最后这$p$个位置也要放物品，答案不足够小），也即将$m$减去$p$并令$n=tm$后的问题
2.若$p>m-k$，即需要保证$t$段中每一段的最后$m-p$个位置必须放物品（否则不难得到最后这$p$个位置要放多于$p-(m-k)$个物品，答案也不足够小）
将最后这$p$个位置补至$m$个，由于补充的位置必须填，因此不影响方案数
换言之，即将$k$减去$m-p$、$m$变为$p$并令$n=(t+1)m$后的问题
最终，时间复杂度即为$o(m \log P)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod 1000000007 4 #define ll long long 5 int t,n,m,k,ans; 6 int qpow(int n,int m){ 7 int s=n,ans=1; 8 while (m){ 9 if (m&1)ans=(ll)ans*s%mod; 10 s=(ll)s*s%mod; 11 m>>=1; 12 } 13 return ans; 14 } 15 int main(){ 16 scanf("%d",&t); 17 while (t--){ 18 scanf("%d%d%d",&n,&m,&k); 19 if (n%m){ 20 int t=n/m,p=n%m; 21 if (p<=m-k)m-=p,n=t*m; 22 else k-=m-p,m=p,n=(t+1)*m; 23 } 24 ans=1; 25 int t=n/m; 26 for(int i=1;i<=k;i++){ 27 int s=1; 28 for(int j=t+1;j<=m-i+t;j++)s=(ll)s*j%mod; 29 for(int j=1;j<=k-i;j++)s=(ll)s*j%mod; 30 for(int j=1;j<=m-i;j++)s=(ll)s*qpow(j,mod-2)%mod; 31 for(int j=t+1;j<=k-i+t;j++)s=(ll)s*qpow(j,mod-2)%mod; 32 ans=(ll)ans*s%mod; 33 } 34 printf("%d\n",ans); 35 } 36 }