阿宅的寒假共有T天，每天有n名亲戚来他家做客，每到饭点时，所有亲戚会来叫在房间里编程的阿宅吃饭,第i名亲戚每隔ai秒会来一次，首次来叫的时间为ai秒(即，第i名亲戚的到访时间为ai,2ai,3ai.）。 阿宅想知道，每一天第k次来叫他的亲戚编号；若同一秒内有多名亲戚同时来叫，则编号较小者优先。
输入描述：
每个测试文件包含多组测试数据。
第一行输入一个整数T（1≤T≤30)，表示寒假天数；
此后对每天数据，描述如下:
在一行上输入两个整数n和k(1≤n≤10^5;1≤k≤10^9)，分别表示亲威人数和要查询的第k次。
在一行上输入n个整数a1,a2,a3（1≤ai≤10^9)，表示第i名亲戚来叫的时间间隔。
除此之外，保证单个测试文件的n之和不超过2× 10^5。
输岀描述：对于每一组测试数据，新起一行。输出一个整数，表示对应天第k次来叫吃饭的亲戚编号。
示例1
输入
- 6
- 3 1
- 1 2 3
- 3 2
- 1 2 3
- 3 3
- 1 2 3
- 3 4
- 1 2 3
- 3 5
- 1 2 3
- 3 6
- 5 7 11
输岀
- 1
- 1
- 2
- 1
- 3
- 1
说明
对于第一、二、三、四、五组测试数据，
每一秒的到访序列依次为：
●第一秒，仅有亲戚1来叫；
●第二秒，亲戚1和2来叫；
●第三秒，亲戚1和3来叫。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 天数
while (T-- > 0) {
int n = sc.nextInt();
long k = sc.nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 二分查找第k次到访发生的时间
long left = 1, right = (long) 1e18;
while (left < right) {
long mid = left + (right - left) / 2;
if (count(a, mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
long t = left; // 第k次到访的时间点
long cntBefore = count(a, t - 1); // t-1 时刻前的访问次数
long need = k - cntBefore; // 第k次是t时刻的第 need 个
// 找到t时刻第 need 个来的亲戚
int ans = -1;
for (int i = 0; i < n; i++) {
if (t % a[i] == 0) {
need--;
if (need == 0) {
ans = i + 1; // 下标从1开始
break;
}
}
}
System.out.println(ans);
}
}
// 统计在时间x内，一共来了多少次
private static long count(long[] a, long x) {
if (x <= 0) return 0;
long res = 0;
for (long v : a) {
res += x / v;
if (res > 1e18) break; // 防溢出保护
}
return res;
}
}
包包有一个长度为n的数组a。你可以将a任意重排，得到一个新的数组，我们称之为a’。定义一个长度为n的数组b，其中bi=MEX(ai’,a2’,···,ai’)。你需要最大化数组b中的元素之和。
你需要输出最大的元素和，以及有多少种可能的重排a，使得中的元素和最大化。由于重排方案数可能很大，你只需要输出其对998244353取模后的结果。
【名词解释】
MEX：整数数组的MEX定义为没有出现在数组中的最小非负整数。例如MEX{1,2，3}=0,MEX{0,2,5} =1。
输入描述
第一行输入一个整数n(1≤n≤2×10^5)，表示数组a的长度。
第二行输入n个整数a1,a2,···,an(0<ai≤10^9)，表示数组a的元素。
输出描述
一行输出两个整数，表示b的元素和以及a的重排数量对998244353取模后的结果。
示例1
输入
- 3
- 1 0 1
输出
- 5 1
说明
将a重排为{0,1,1}后，数组b为{1,2,2}，元素和为5。可以证明不存在一个重排使得数组b的元素和大于5，且仅有这一种重排方案满足条件。
import java.util.*;
public class Main {
static final long MOD = 998244353;
static long[] fac, invFac;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 读取数组长度
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
// 预处理阶乘和逆元阶乘
precomputeFactorial(n);
// 统计每个元素出现次数
Map<Integer, Integer> count = new HashMap<>();
for (int x : a) count.put(x, count.getOrDefault(x, 0) + 1);
// 找 MEX
int mex = 0;
while (count.containsKey(mex)) mex++;
// 计算最大和：sum(b) = k*n - k*(k-1)/2
long maxSum = (long) mex * n - (long) mex * (mex - 1) / 2;
// 计算排列数
// 前 mex 个数固定顺序（0..mex-1各出现一次），剩余元素自由排列
long ways = fac[n - mex]; // 剩余元素全排列
// 对前 mex 个可能重复的元素，除去重复排列
for (int i = 0; i < mex; i++) {
int c = count.getOrDefault(i, 0);
if (c > 1) {
ways = ways * invFac[c - 1] % MOD;
}
}
System.out.println(maxSum + " " + ways);
}
// 预处理阶乘和逆元阶乘
static void precomputeFactorial(int n) {
fac = new long[n + 1];
invFac = new long[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
invFac[n] = modInverse(fac[n], MOD);
for (int i = n - 1; i >= 0; i--) invFac[i] = invFac[i + 1] * (i + 1) % MOD;
}
// 快速幂求逆元
static long modPow(long a, long e, long mod) {
long res = 1;
a %= mod;
while (e > 0) {
if ((e & 1) == 1) res = res * a % mod;
a = a * a % mod;
e >>= 1;
}
return res;
}
static long modInverse(long a, long mod) {
return modPow(a, mod - 2, mod);
}
}
Comments NOTHING