题目大意

一共有q+1个人跟你抢票，有些人可以抢两种票，有一些只能抢第二组票，求出你能抢到票的排列组合数量

思路

预处理组合数和排列数： 由于数据量较大（最大到3000），可以使用杨辉三角预处理出组合数 C(n, m) 和排列数 A(n, m)，以便在后续计算中快速查询。

分配抢票玩家： 将抢票玩家分为两类：可以抢两档票的玩家（天数 <= t）和只能抢第二档票的玩家（天数 > t）。统计这两类玩家的数量分别为 n1 和 n2。

枚举抢票情况：

使用双重循环来枚举： 1.第一重循环枚举在小塔前面、且抢第一档票的玩家数 i。

2.第二重循环枚举在小塔前面、抢第二档票的玩家数 j。

最后通过组合数计算出 n1 中选 i 个玩家以及 n2 中选 j 个玩家的方案数，并累乘对应排列数，表示小塔在这两类玩家后的抢票顺序总数。 累加满足条件的排列数： 根据 i 和 j 所需的票数来判断是否足够，累加所有满足小塔能够抢到票的排列数。 最后将累加值对 mod 取模，得到最终结果即可。

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int N = 3005;
int C[N][N], A[N][N];

void init() {
    for (int i = 0; i < N; ++i) {
        C[i][0] = 1;   // C(n, 0) = 1
        A[i][0] = 1;   // A(n, 0) = 1
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            A[i][j] = int(1LL * A[i][j-1] * (i - j + 1) % MOD);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();  // 初始化杨辉三角

    int n, m, q, t;
    cin >> n >> m >> q >> t;
    vector<int> d(q);
    for (int i = 0; i < q; ++i) {
        cin >> d[i];
    }

    int n1 = 0;
    for (int x : d) if (x <= t) ++n1;
    int n2 = q - n1;

    long long ans = 0;
    if (n > t) {
        // 只能先抢第一档，第一档没了再去第二档
        for (int i = 0; i <= n1; ++i) {
            for (int j = 0; j <= n2; ++j) {
                int now = max(i - m, 0) + j;
                if (now < m) {
                    ans = (ans
                        + 1LL * C[n1][i] * C[n2][j] % MOD
                        * A[i+j][i+j] % MOD
                        * A[q-i-j][q-i-j] % MOD
                    ) % MOD;
                }
            }
        }
    } else {
        // 可以直接抢第一档
        for (int i = 0; i <= n1; ++i) {
            for (int j = 0; j <= n2; ++j) {
                int now = i + j;
                if (now < 2 * m) {
                    ans = (ans
                        + 1LL * C[n1][i] * C[n2][j] % MOD
                        * A[i+j][i+j] % MOD
                        * A[q-i-j][q-i-j] % MOD
                    ) % MOD;
                }
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

python

MOD = 10**9 + 7
N = 3005

# 初始化组合数和排列数
C = [[0] * N for _ in range(N)]  # C(n, m) 表示组合数
A = [[0] * N for _ in range(N)]  # A(n, m) 表示排列数

# 使用杨辉三角来计算组合数 C(n, m) 和排列数 A(n, m)
def init():
    for i in range(N):
        C[i][0] = 1  # C(n, 0) = 1
        A[i][0] = 1  # A(n, 0) = 1
        for j in range(1, i + 1):
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
            A[i][j] = (A[i][j - 1] * (i - j + 1)) % MOD

# 主程序
def main():
    init()  # 初始化杨辉三角

    n, m, q, t = map(int, input().split())  # 输入 n, m, q, t
    d = list(map(int, input().split()))  # 输入 q 个玩家的登陆天数
    
    n1 = sum(1 for x in d if x <= t)  # 统计 <= t 的玩家数量
    n2 = q - n1  # 统计 > t 的玩家数量

    ans = 0
    if n > t:  # 小塔只能抢第二档位的票
        for i in range(n1 + 1):  # 遍历 <= t 的玩家分配到第一档位的票数量
            for j in range(n2 + 1):  # 遍历 > t 的玩家分配到第二档位的票数量
                now = max(i - m, 0) + j  # 当前第一档票被抢完后，第二档位的需求量
                if now < m:  # 如果第二档票还足够，则统计这种排列方式
                    ans = (ans + C[n1][i] * C[n2][j] % MOD * A[i + j][i + j] % MOD * A[q - i - j][q - i - j] % MOD) % MOD
    else:  # 小塔可以抢第一档位的票
        for i in range(n1 + 1):
            for j in range(n2 + 1):
                now = i + j  # 计算所需的总票数
                if now < 2 * m:  # 如果总票数足够
                    ans = (ans + C[n1][i] * C[n2][j] % MOD * A[i + j][i + j] % MOD * A[q - i - j][q - i - j] % MOD) % MOD

    print(ans)  # 输出结果

if __name__ == "__main__":
    main()

java

```java
import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;
    static final int N = 3005;
    
    static long[][] C = new long[N][N]; // C(n, m) 表示组合数
    static long[][] A = new long[N][N]; // A(n, m) 表示排列数
    
    // 使用杨辉三角来计算组合数 C(n, m) 和排列数 A(n, m)
    static void init() {
        for (int i = 0; i < N; i++) {
            C[i][0] = 1;  // C(n, 0) = 1
            A[i][0] = 1;  // A(n, 0) = 1
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
                A[i][j] = (A[i][j - 1] * (i - j + 1)) % MOD;
            }
        }
    }
    
    public static void main(String[] args) {
        init();  // 初始化杨辉三角
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int t = sc.nextInt();
        
        int n1 = 0, n2 = 0;  // n1 统计 <= t 的玩家，n2 统计 > t 的玩家
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt();
            if (x <= t) {
                n1++;
            }
        }
        n2 = q - n1;  // n2 即为 > t 的玩家数量

        long ans = 0;
        if (n > t) {  // 小塔只能抢第二档位的票
            for (int i = 0; i <= n1; i++) {  // 遍历 <= t 的玩家分配到第一档位的票数量
                for (int j = 0; j <= n2; j++) {  // 遍历 > t 的玩家分配到第二档位的票数量
                    int now = Math.max(i - m, 0) + j;  // 当前第一档票被抢完后，第二档位的需求量
                    if (now < m) {  // 如果第二档票还足够，则统计这种排列方式
                        ans += (((C[n1][i] * C[n2][j] % MOD) * A[i + j][i + j] % MOD) * A[q - i - j][q - i - j] % MOD);
                        ans %= MOD;
                    }
                }
            }
        } else {  // 小塔可以抢第一档位的票
            for (int i = 0; i <= n1; i++) {
                for (int j = 0; j <= n2; j++) {
                    int now = i + Math.min(m, j);  // 计算所需的总票数
                    if (now < 2 * m) {  // 如果总票数足够
                        ans += (((C[n1][i] * C[n2][j] % MOD) * A[i + j][i + j] % MOD) * A[q - i - j][q - i - j] % MOD);
                        ans %= MOD;
                    }
                }
            }
        }

        System.out.println(ans);
        sc.close();
    }
}

题目内容

米小游是一位《原神》的全勤玩家，但她却抢不到《原神FES》的门票，因此决定开发一款有利于全勤玩家的抢票系统。

新的抢票系统如下：将票分成$2$个档位，每个档位的票数都为 $m$，游戏运营了 $n$天，设置一个抢票参数 $t$。

抢票玩家的游戏登陆天数为 $x$，若 $x ≤ t$，则优先分配第$1$档位的票，若第$1$档位已经没有票了，则分配第 $2$档位的票，若第$2$档位也没有票，则此玩家没有抢到票；若 $x > t$，则玩家只能分配第$2$档位的票，若第$2$ 档位没有票，则此玩家没有抢到票。

米小游是全勤玩家，登陆天数为 $n$。现在有$q$个玩家在和米小游抢票，第$i$个玩家的登陆天数为$d_i$。抢票的先后顺序可以看成是一个长度为$q+1$的排列，但具体的排列未知。

米小游想知道有多少种排列可以使得她至少抢到一张票。

输入描述

第一行输入四个整数：

$n, m, q, t$($1 ≤ n, m, q ≤ 10^3, 1 ≤ t ≤ n$)：表示游戏运营天数、每个档位的票数、抢票玩家数、抢票参数。

第二行输入$q$整数 $d_i$($1 ≤ d_i ≤ n$)：表示玩家的游戏登陆天数。

输出描述

输出一个整数，表示答案。由于这个数字可能很大，因此需要输出这个数字对$10^9 + 7$取模后的结果。

样例1

输入

2 1 2 2
1 2

输出

4