专栏文章

题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

LLinkCatTree
P14636题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mimygu00
此快照首次捕获于
2025/12/01 17:37
3 个月前
此快照最后确认于
2025/12/01 17:37
3 个月前
查看原文
第一次正赛切紫，留念。
以下的 aia_i 均已经降序排序方便考虑。
正难则反，考虑统计贪心策略不优的方案数。首先手动模拟一下样例，我们发现当且仅当一个较大的 aia_i 因为 wi=2w_i=2 而被较后选择，而后面的某个 aj>ai2(wj=1)a_j>\dfrac{a_i}2(w_j=1) 在被选择后恰好 m=1m=1 导致 aia_i 没有被选择使得贪心策略不优（为什么有大于的限制？因为 aja_j 要在 aia_i 前被选择）。
我们讨论一下 m=1m=1 时如果后面还有 ak(wk=1)a_k(w_k=1) 被抉择的情况，发现这样的 kk 的范围是一个 [k0,n][k_0,n] 的形式，可以在从小到大枚举 jj 的时候双指针顺便做掉。显然 kk 即后面的 aa 其 ww 均可随意抉择，所以考虑直接枚举 ii 和 jj，其就是 w1⋯wjw_1 \cdots w_j 的方案数与 2n−k0+12^{n-k_0+1} 的乘积（此时我们已经钦定 wi=2,wj=1,wj+1⋯wk−1=2w_i=2,w_j=1,w_{j+1} \cdots w_{k-1}=2）。
我们发现我们需要在决策完 aja_j 时 mm 恰为 11，那么我们需要在 11 到 jj 剩余的 j−2j-2 个位置上填 ww，这个直接组合意义是不太好做的。我们再考虑枚举 i+1⋯j−1i+1 \cdots j-1 中有多少个 wk=1w_k=1 即这些 aka_k 会在 aja_j 前被选择，假设有 xx 个这样的 k(wk=1)k(w_k=1)。我们发现在 ii 之前的无论 ww 为 11 或 22 都一定会被选择，也就是说我们要求 w1⋯wi−1w_1 \cdots w_{i-1} 的和为 m−x−2m-x-2，那么我们可以把这两部分组合意义分开计算：
∑x=0j−i−1(j−i−1x)×(i−1m−i−1−x)\sum_{x=0}^{j-i-1} \binom{j-i-1}{x} \times \binom{i-1}{m-i-1-x}
显然直接枚举 i,j,xi,j,x 是 O(n3)\mathcal{O}(n^3) 的，考虑优化上面这个式子。这里引用一句不知道谁说的话：代数推导天地灭，组合意义保平安。我们考虑该式的实际组合意义：共 (j−i−1)+(i−1)(j-i-1)+(i-1) 个球，在前 j−i−1j-i-1 个球中取 xx 个，在后 i−1i-1 个球中取 m−i−1−xm-i-1-x 个，枚举 xx，也就是说上式等价于：
(j−2m−i−1)\binom{j-2}{m-i-1}
于是我们可以省去枚举 xx 的时间复杂度，O(n2)\mathcal{O}(n^2) 可通过本题。
CPP
#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x=0,ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
	return x;
}

using ll=long long;
const ll mod=998244353;
const int N=5005;
int c,T,n,m;
struct Candy {
	int val,id;
	Candy(int val=0,int id=0) {this->val=val,this->id=id;}
	inline bool operator <(const Candy& tmp) const {
		if(val==tmp.val) return id<tmp.id;
		return val>tmp.val;
	}
} a[N];

inline ll quickpow(ll base,ll p) {
	ll tmp=1;
	for(;p;p>>=1) {
		if(p&1) tmp=tmp*base%mod;
		base=base*base%mod;
	}
	return tmp;
}
ll pw[N],fact[N],inv[N];
inline void init() {
	static const int s=5000;
	pw[0]=fact[0]=inv[0]=1;
	for(int i=1;i<=s;i++) {
		pw[i]=pw[i-1]<<1;
		if(pw[i]>=mod) pw[i]-=mod;
	}
	for(int i=1;i<=s;i++) {
		fact[i]=fact[i-1]*i%mod;
		inv[i]=quickpow(fact[i],mod-2);
	}
	return ;
}
inline ll C(int n,int m) {
	if(n<0||m<0||n<m) return 0;
	return fact[n]*inv[m]%mod*inv[n-m]%mod;
}

int main() {
	c=read(),T=read(),init();
	while(T--) {
		n=read(),m=read();
		for(int i=1;i<=n;i++) a[i].val=read(),a[i].id=i;
		sort(a+1,a+1+n); ll ans=0;
		for(int i=1;i<n;i++) {
			int q=lower_bound(a+1,a+1+n,Candy(a[i].val>>1,0))-a;
			for(int j=i+1,k=n;j<q;j++) {
				if(a[j].val==a[i].val) continue ;
				while(k>=q&&a[j].val+a[k].val<a[i].val) k--;
				(ans+=C(j-2,m-i-1)*pw[n-k])%=mod;
			}
		}
		if((ans=pw[n]-ans)<0) ans+=mod;
		printf("%lld\n",ans);
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...