题解：P14636 [NOIP2025] 清仓甩卖 / sale

场上做法

先将

a_i

从大到小排序，下面用1表示

w_i=1

的物品，2表示

w_i=2

的物品

容易想到买不到最大当且仅当最后的两个1换成最大的没选的2更优。设i为最大的没选的2，j,k依次为倒数第二，倒数第一个1，则需满足

a_i<a_j*2,a_j+a_k<a_i

。

考虑钦定

j

,双指针出满足第一个柿子的最小的

i

,再枚举

i

,双指针出满足第二个柿子的最小的

k

,则可将序列分为

i

前面，

i

到

j

j

到

k

k

后面四段，记他们的长度分别为。

c_1,c_2,c_3,c_4

（每一段都不含

i,j,k

）。

注意到第3段一定为2，第4段可任取，第一段

w

的总和加上第二段1的个数必为

m-2

,故1,2段和第4段可分开讨论。

考虑1,2段，设第一段有x个2，则第一段总和为

c_1+x

,第二段1的个数为

m-2-c_1-x

,种类数即为

\sum{\begin{pmatrix}c_1\\x\\\end{pmatrix} \times \begin{pmatrix}c_2\\ m-2-c_1-x\\\end{pmatrix}}

,范德蒙德卷积即为

\begin{pmatrix}c_1+c_2\\m-2-c_1\end{pmatrix}

接下来考虑第4段，设

k

最大可取到

now

,如果没有合适的k则

now=n+1

,则总方案数为

\sum_{i=0}^{n-now+1} 2^i+1

,加1是因为后面可能没有1，但注意如果

a_i=a_j

则无法加1，为0。注意到其他情况下这个柿子即为

2^{n-now+1}

。

接下来把刚才得到的两个柿子相乘后累加即可，时间复杂度

O(\sum{n^2})

，少爷机上应该能过。

cpp

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3fll

const int N=5e4+10;
const ll mod=998244353;

ll a[N],fac[N],inv[N],pw[N],n,m,T,Type;

ll qp(ll x,ll y)
{
	ll sum=1;
	while(y)
	{
		if(y&1) sum=sum*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return sum;
}

void init()
{
	fac[0]=pw[0]=1;
	for(int i=1;i<=5e4;i++)
	{
		fac[i]=fac[i-1]*i%mod;
		pw[i]=pw[i-1]*2%mod;
	}
	inv[50000]=qp(fac[50000],mod-2);
	for(int i=49999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> Type >> T;
	init();
	while(T--)
	{
		cin >> n >> m;
		for(int i=1;i<=n;i++) cin >> a[i];
		sort(a+1,a+n+1);
		for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]);
		ll ans=0,pos=1;
		for(int i=1;i<=n;i++)
		{
			while(a[pos]>=a[i]*2) pos++;
			int now=n+1;
			for(int j=i-1;j>=pos;j--)
			{
				while(now>1&&a[i]+a[now-1]<a[j]) now--;
				ll c1=j-1,c2=i-j-1;
				if(a[j]>a[i]&&m-2-c1>=0&&c1+c2>=m-2-c1)
				{
					ans=(ans+inv[m-2-c1]*inv[c1*2+c2-m+2]%mod*fac[c1+c2]%mod*pw[n-now+1]%mod)%mod;
				}
			}
		}
		cout << (pw[n]+mod-ans)%mod << '\n';
	}
	return 0;
}

题解：P14636 [NOIP2025] 清仓甩卖 / sale

文章操作

cpp

相关推荐

评论

题解：P14636 [NOIP2025] 清仓甩卖 / sale