[NOIP2025] 清仓甩卖 / sale

lovely_nst · 2025-11-30 20:47:29 · 题解

考虑算不合法的情况。显然是买了 w=1 的 i,j，然后存在一个没有买的 w=2 的 k，然后满足 a_i+a_j<a_k。

考虑对这个计数，首先对 a 升序排序，然后枚举 i（钦定 i>j）和 k。显然要满足以下几个条件：

因此要满足 \dfrac{a_k}2<a_i<a_k。

考虑分讨：

• 对于 p>k，此时无论 w 为啥，p 的性价比均高于 k，这样的 p 有 n-k 个，w=1 时花费 1，w=2 时花费 2。

• 对于 i<p<k，当 w=1 时性价比更高，反之更低，因此当 w=1 时花费 1，而 w=2 时选不到，因此花费 0。

• 对于 \dfrac{a_k}2<a_p<a_i，若此时 w=1，a_p+a_i 一定大于 a_k，显然无解。因此只可能 w=2，性价比更低，选不到，因此花费 0。

以上情况在贡献全部加完后会剩余 1 的钱数（若更多就可以加入 w=2 了，），减去 i 的花费，因此总共花费 m-2 的钱数。只有前两种情况有贡献，分别为花费 1/2 和 0/1，考虑减掉前面的和。第一种情况有 n-k 个，第二种情况有 k-i-1 个，总共 n-i-1 个。最终就是求有 n-i-1 个数 0/1，求总和为 m-n+k-2 的方案数，这个用组合数很好求，就是 $\dbinom {n-i-1}{m-n+k-2}。（千万别写反了）

剩下的情况，就是找到最大满足 a_q+a_i<a_k 的 q，此时 p>q 的位置只能 w=2，因为若有 1 就会使其合法。而前 q 位如何选都可以，因此方案数为 2^q。

因此方案数为 2^p\dbinom {n-i-1}{m-n+k-2}。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5005 , M = 10005 , mod = 998244353;
int cid , T;
int n , m;
int a[N] , fr[M] , inv[M] , pw[M];
int power (int x , int y)
{
    int mul = 1;
    while (y)
    {
        if (y & 1) mul = mul * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return mul;
}
int C (int x , int y)
{
    if (x < y) return 0;
    return fr[x] * inv[y] % mod * inv[x - y] % mod;
}
void Add (int &x , int y)
{
    x += y;
    if (x >= mod) x -= mod;
}
signed main ()
{
    fr[0] = inv[0] = pw[0] = 1;
    for (int i = 1;i < M;i ++) fr[i] = fr[i - 1] * i % mod , pw[i] = (pw[i - 1] << 1) % mod;
    inv[M - 1] = power (fr[M - 1] , mod - 2);
    for (int i = M - 2;i >= 1;i --) inv[i] = inv[i + 1] * (i + 1) % mod;
    ios::sync_with_stdio (0);
    cin.tie (0) , cout.tie (0);
    cin >> cid >> T;
    while (T --)
    {
        cin >> n >> m;
        for (int i = 1;i <= n;i ++)
            cin >> a[i];
        sort (a + 1 , a + n + 1);
        int ans = 0;
        for (int i = 1;i <= n;i ++) // w_i = 1
        {
            int p = 0;
            for (int j = i + 1;j <= n;j ++) if (a[i] < a[j] && a[j] < (a[i] << 1)) // w_j = 2
            {
                // k > j : n - j  (1 / 2)
                // i < k < j : j - i - 1 (0 / 1)
                // sum = m - 2
                int s1 = n - j , s2 = j - i - 1;
                if (m - 2 - s1 < 0) continue;
                // a_p + a_i < a_j
                while (p < n && a[p + 1] + a[i] < a[j])
                    p ++;
                int w = C (n - i - 1 , m - 2 - (n - j));
                Add (ans , pw[p] * w % mod);
            }
        }
        cout << (pw[n] - ans + mod) % mod << '\n';
    }
    return 0;
}