NOIP_2025_T2
druzewang
·
·
题解
闲话
赛时 1h 思考 m = 2 的部分分，结果发现好像可以拓展到所有的 m，然后就花了 1h 写了个假的写法，发现之后，又用了 2h，去写正解，极限写完。
感谢zcq巨佬祝我破鼎。（虽然没帮助我什么）
写法
jzp 曾经说过，一个好的题目，一定能从部分分来启发正解，对于这道题，我们首先把目光放在数据点 7,8,9,14,15，发现一个共同点，居然是 m = 2！！！
对于只有两块钱的情况：
- 购买两个花费为 w = 1（或者一个，有可能不够）。
- 购买一个花费为 w = 2。
不妨设两个 w = 1 的是 x,y(x < y) 一个 w = 2 的是 z。
那么如果现在购买 x,y，不合法的情况也就是 x + y < z，但是我们有要先买 y，所以有 y > x > \frac{z}{2} 或 y > \frac{z}{2} > x。
-
-
现在购买 z，那么就是 z < x + y 并且 \frac{z}{2} > x,y，但是并不满足 \frac{x}{2} + \frac{y}{2} > \frac{z}{2} > x,y，所以舍掉。
综上，只有 m = 2 并且 y > \frac{z}{2} > x 才是不行的方案
我们居然退出来了 m = 2 的办法，那我们试着推广一下？
那也就是 z 会被在性价比比 \frac{z}{2} 要大的那些正好卡到 m - 1 才是不行的方案数，所以枚举以下就可以了！O(n^3) 成功拿到 52 pts，我可真厉害。
正解（过了民间数据）
发现直接计算合法方案不太行，直接考虑容斥，我们只需要统计上述不合法方案数，使用 2^n - 不合法方案数就可以了。
为了更好理解些，直接使用 O(n) 的复杂度来枚举被卡掉的点 i，这样才好统计填补的点 j。
将所有 a_i 从大到小排序，这时候我们会发现可以把其他的点都归类到三种集合中。
- 集合 A = \{(i,j)|i < j \land a _ i < a _ j\}：
- 无论 w_j 是 1 还是 2，性价比都排在 i 的前面。这些糖果一定在 i 之前被考虑。
- 集合 B = \{(i,j)| i > j \land a _ i < 2a _ j\}：
- 若 w_j = 1，那么性价比比 i 要高，排在 i 的前面。
- 若 w_j = 2，那么性价比比 i 要低，排在 i 的后面。
- 集合 C = \{(i,j)|i > j \land a _ i > a _ j\}：
- 不管 w_j 是 1 还是 2，性价比都比 i 第，永远排在 i 的后面。
对于固定的 i(w_i = 2)，要使其成为因为没钱被调过的糖果，就用到了我们上面的理论——性价比比 i 高的正好花费了 m - 1 元钱，包括 A 中的所有糖果，花费 w_j，以及 B 中 w_j = 1 的糖果。
设 C_A = |A|,C_B = |B|，设 K_A 是 A 中所有 w_j = 2 的个数， K_B 是 B 中所有 w_j = 1 的个数。
总花费 = (C_A - K_A) \times 1 + K_A \times 2 + K_B \times 1 = C_A + K_A + K_B。
方案数变成了从 $C_A + C_B$ 个位置中选出 $m - 1 - C_A$ 个位置的方案数：
$$
\left ( _ {m - 1 - N_A} ^ {C_A + C_B} \right)
$$
在 $i$ 被跳过之后，只剩下一块钱，$B$ 中剩余的糖果一定是 $w_j = 2$（不然前面就已经选走了），买不起，跳过。
$C$ 中的糖果按照顺序考虑：
- 如果 $w = 2$，那么买不起，跳过；
- 遇到的第一个 $w = 1$ 糖果就是 $j$；
- 如果遍历完也没看到 $w = 1$ 的，那么就没有 $j$。
那我们找到了固定的 $i,j$，方案是不合法的仅当：已经存在购买过的一元糖果 $k$，使得 $a_k < a_i - a_j$。
其中 $k$ 可以来自 $A (w = 1)$ 或者 $B (w = 1)$。
对于所有满足 $a_k < a_i - a_j$ 的时候选择 $k$，那么 $w_k$ 必须选择 2（如果在 $A$）或者不能选择 1（如果在 $B$ 中，也就是必须是 $2$）。
那我们可以记录一个阈值 $D = a_i - a_j$ ，设 $S = A \cup B$ 中满足 $a_k < D$ 的元素集合。
要避免交换，必须强制 $S$ 中的所有元素 $w = 2$，这回固定 $S$ 中元素对 $K_A,K_B$ 的贡献：
- $A \cap B$ 中的元素必须是 $2 \Rightarrow K_A$ 增加 $|A \cap S|$。
- $B \cap S$ 中的元素必须是 $2 \Rightarrow K_B$ 其实就是不增加，因为 $K_B$ 统计的是 $w = 1$。
剩余任意可选的：$(C_A + C_B) - |S|$。
需要统计的方案数：$(m - 1 - C_A) - |A \cap S|$。
方案数：
$$
\left ( _ {m - 1 - C_A - |A \cap S|} ^ {C_A + C_B - |S|} \right)
$$
于是当前 $(u,v)$ 的贡献：
$$
\left(
\left( _ {m - 1 - C_A} ^ {C_A + C_B}\right) - \left( _ {m - 1 - C_A - |A \cap S|} ^ {C_A + C_B - |S|} \right) \right) \times 2^r
$$
其中 $r$ 表示 $j$ 之后的 $C$ 中可以任意取的值。
复杂度 $O(T \times n^2)$。
切出来了！！！（虽然用了 $4h$）
# Code
```cpp
#include<bits/stdc++.h>
using namespace std;
/*
剩余2元时
只有可能1把更有的2给卡住
也就是当前1的最大值的性价比比2的最大值的性价比要大
1:x,y
2:z
y > z/2 && x + y < z
如果满足上述条件，那就是完damn了
剩余大于2元时
总是可以转换成2元的效果
考虑枚举z
O(n^2)可过吗？？？ sigma_n <= 5*10^4 应该差不多吧，？。万一数据卡掉那不就直接炸了。。。。。。
OOOOO 说了n <= 5000 ，所以应该差不多大概好像可以。
那么总合法方案数量就是总方案数(2^n) - 总不合法方案数
求一下上面那个条件就可以了，枚举？
欸？在上述中x可能不存在
现在枚举被卡掉的2
首先降序排序
当前第i个为ai
设A集合为所有的j且aj >= ai
设B集合为所有的j且j > i && 2aj >= ai(也就是选2排在i后，选1排在i前)
设C集合为所有的j且j > i && 2aj <= ai(也就是不论怎样都要在i的后面)
设Na = |A|,Nb = |B|,kA中取w=2的个数，kB为B中取w=1的个数。
总花费：(Na - kA) * 1 + kA * 2 + kB * 1 = Na + kA + kB
Na + kA + kB = m - 1 => kA + kB = m - 1 - Na
方案数为从 Na + Nb 个位置中选m - 1 - Na个位置贡献额外全值的方案数：
C_{m - 1 - Na}^{kA + kB}
在u被跳过后，剩下的钱只有1
B中剩余的糖果必然是w=2，否则会在u的前面买，那就没钱了
C中的糖果按照顺序考虑
如果也是w=2，买不起，跳过
遇到的第一个w=1的糖果也就是v
如果遍历完c也没有w=1的糖果，也就是v不存在
对于固定的uv，方案是坏的仅当：存在已经购买的一元糖果z，az < au + av
其中z可以来自AorB
所以对于当前uv的贡献，也就是 ([ka + kb,m - 1 - Na] - [(Na + Nb - |S|),(m - 1 - Na) - |A U S|]) * 2^c
*/
#define int long long//十年oi一场空，不开__见__
#define O(i,e,r) for (register int i = (e);i <= (r);++i)
#define U(i,e,r) for (register int i = (e);i >= (r);--i)
#define I(e,r) for (auto e : (r))
#define gc getchar
#define mul(a,b) a = (a * b) % mod
#define add(a,b) a = (a + b) % mod
#define sub(a,b) a = (a - b + mod) % mod
#define fi first
#define se second
const int mod = 998244353;
const int N = 200000;
int Case,T_T,n,m,tot;
int a[N + 5],fact[N + 5],inv[N + 5],finv[N + 5],qp2[N + 5];
inline void read(int &x){
x = 0;
int f = 1;
char c = gc();
while (c < '0' || c > '9'){
if (c == '-') f = -1;
c = gc();
}
while (c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c - 48);
c = gc();
}
x *= f;
}
inline bool cmp(int x,int y){return x > y;}
inline int qpow(int x,int y){
int base = x,ans = 1;
while (y){
if (y & 1) mul(ans,base);
mul(base,base);
y >>= 1;
}
return ans;
}
inline int Cc(int x,int y){
if (y < 0 || y > x) return 0;
return fact[x] * finv[y] % mod * finv[x - y] % mod;
}
inline void init(){
fact[0] = finv[0] = qp2[0] = 1;
O(i,1,N){
fact[i] = fact[i - 1] * i % mod;
finv[i] = qpow(fact[i],mod - 2);//超慢逆元
qp2[i] = qp2[i - 1] * 2 % mod;
}
/*
ai + b = 0
a * invi * i * invb + invi * invb * b = 0
a * invb + invi = 0
invi = -b * inva
*/
}
signed main(){
//zcq_qwq AK IOI !!!!!! zcq巨佬保我这道题AC！！！！！
// freopen("sale.in","r",stdin);
// freopen("sale.out","w",stdout);
read(Case), read(T_T);
init();
while (T_T--){
read(n), read(m), tot = 0;
O(i,1,n) read(a[i]);
sort(a + 1,a + n + 1,cmp);
O(i,1,n){
int idx = i + 1;
while (idx <= n && 2 * a[idx] > a[i]) ++idx;//寻找B集合的
int A = i - 1,B = idx - 1 - i,C = n - idx + 1;//A，B，C集合的
int tmp = Cc(A + B,m - 1 - A);
// cout << A << ' ' << B << ' ' << C << ' ' << idx << ' ' << tmp << '\n';
if (tmp == 0) continue;
vector <pair<int,int> >vec;
int x1 = 1,x2 = i + 1;
while (x1 < i && x2 < idx){//双指针
if (a[x1] >= a[x2]){
vec.push_back({a[x1],0});
++x1;
}else{
vec.push_back({a[x2],1});
++x2;
}
}//0表示A集合的，1表示B集合的
while (x1 < i){
vec.push_back({a[x1],0});
++x1;
}
while (x2 < idx){
vec.push_back({a[x2],1});
++x2;
}
int k = vec.size() - 1,kA = 0,kB = 0;
O(j,0,C){
int val = 0;
if (j < C) val = a[idx + j];
int D = a[i] - val;
// cout << a[i] << ' ';
// cout << val << ' ' << D << ' ' << k << '\n';
while (k >= 0 && vec[k].fi < D){
if (vec[k].se == 0) ++kA;
else ++kB;
--k;
} //统计vec里面的A，B元素
int b = (tmp - Cc(A + B - kA - kB,m - 1 - A - kA) + mod) % mod;
if (b > 0){
if (j < C) tot = (tot + b * qp2[C - 1 - j]) % mod;
else tot = (tot + b) % mod;
}
}
// cout << tot << '\n';
}
cout << (qp2[n] - tot + mod) % mod << '\n';
}
}
```
# 总结
是个题目，并且大于等于红，小于等于黑。
Q_Q 真的不是我用 $pq2$ 卡常数，不然会真的 [TLE](https://www.luogu.com.cn/record/250816958)。