[NOIP2025] 清仓甩卖 / sale

考虑算不合法的情况。显然是买了

w=1

的

i,j

，然后存在一个没有买的

w=2

的

k

，然后满足

a_i+a_j<a_k

。

考虑对这个计数，首先对

a

升序排序，然后枚举

i

（钦定

i>j

）和

k

。显然要满足以下几个条件：

$a_i<a_k$ ，这样才有替换后更优的可能。
$\dfrac{a_k}2<a_i$ ，此时 $i$ 的性价比比 $j$ 高，会优先选 $i$ 。

因此要满足

\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

CPP

#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;
}

[NOIP2025] 清仓甩卖 / sale

文章操作

AC Code

相关推荐

评论

[NOIP2025] 清仓甩卖 / sale