题意：

长度为$n$的队列，每轮出队队头，再在剩下$k-1$人中选$m-1$人出队，问出队结果集大小。

前置知识：

组合数，快速幂

分析：

无论上一轮怎么出队，当前这一轮的结果集大小都不会变，因此我们可以利用递推；

注意一下剩余人数可能不足$k$人的变化，设$f_n$表示$m$，$k$，确定的情况下，$n$个人的出队结果集，则简单的可以写成：

$$f_n = C_{min(n, k)-1}^{m-1}*f_{n-m}$$

注意到这个递推显然是可以分成两部分的，取决于$min(n,k)$；

因为$n$每次减少$m$，那么$min(n,k)$取$k$的次数$x$可以直接计算得到：

$$n-xm<=k \\ x>=\frac{n-k}{m} \\ x_{min}=\lceil\frac{n-k}{m}\rceil$$

那么式子变成

$$f_n = [C_{k-1}^{m-1}]^{x}*f_{n-xm}$$

乘号左边快速幂算一下$O(logn)$；右边已知了$n-xm<=k$，则暴力计算或预处理$O(k)$。

时间复杂度：

预处理$O(k^2)$，每个$Case$为$O(k)$，共$T$个。

总的来说：$O(k^2)$

参考代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5010, mod = 1e9 + 7;

int n, m, k;
int c[N][N];

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}

void init() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    init();

    int T_T = 1;
    cin >> T_T;
    while (T_T--) {
        cin >> n >> m >> k;
        int x = n > k ? (n - k + m - 1) / m : 0;  // x不能负
        int ans = qmi(c[k - 1][m - 1], x);
        n -= x * m;
        while (n > m) {
            ans = ans * c[n - 1][m - 1] % mod;
            n -= m;
        }
        cout << ans << "\n";
    }
    return 0;
}

其他

$f_{n-xm}$能不能算快点？