#P2179. 2024.10.12-第3题-米小游玩原神
-
3000ms
Tried: 83
Accepted: 10
Difficulty: 7
所属公司 :
米哈游
时间 :2024年10月12日
2024.10.12-第3题-米小游玩原神
题目大意
一共有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个玩家的登陆天数为di。抢票的先后顺序可以看成是一个长度为q+1的排列,但具体的排列未知。
米小游想知道有多少种排列可以使得她至少抢到一张票。
输入描述
第一行输入四个整数:
n,m,q,t(1≤n,m,q≤103,1≤t≤n):表示游戏运营天数、每个档位的票数、抢票玩家数、抢票参数。
第二行输入q整数 di(1≤di≤n):表示玩家的游戏登陆天数。
输出描述
输出一个整数,表示答案。由于这个数字可能很大,因此需要输出这个数字对109+7取模后的结果。
样例1
输入
2 1 2 2
1 2
输出
4