专栏文章

题解：P12251 [科大国创杯初中组 2025] 抽卡【暂无数据】

PPurslaneM2GA
P12251题解参与者 19已保存评论 18

文章操作

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

当前评论
18 条
当前快照
1 份
快照标识符
@mipjn3cv
此快照首次捕获于
2025/12/03 13:05
3 个月前
此快照最后确认于
2025/12/03 13:05
3 个月前
查看原文

Solution

来个拉格朗日插值优化 DP 的方法。现在的安徽小朋友越来越不容易了，一年一年的上强度。
阅读题面的时候一眼看到三个可：，非常有趣。
可能会有一些小朋友阅读这篇文章，所以我写的详细一些。
首先，考虑固定局面下小可可怎么取牌可以获得最大收益。
假设有一个集合 U={1,2,3,⋯ ,2n}U=\{1,2,3,\cdots,2n\} 表示牌的编号（注意和牌上的值并不相通），小可可选取的牌的集合 CC 是 UU 的一个大小为 nn 的子集。在这 (2nn)\binom{2n}{n} 个子集中，我们需要选出合法的且代价最大的那一个。
为什么要强调“合法”呢？比如，小可可并不能选出前 nn 张牌（n≥2n \ge 2），因为波特肯定会在第一张牌和第二张牌中选出一个。
我们断言：小可可取出的集合 CC 合法，当且仅当 ∀1≤k≤n\forall 1 \le k \le n，CC 中小于等于 2k2k 的牌的个数 ≤k\le k。使用数学归纳法容易证明。
那么不妨设小可可初始的牌放在 11，33，⋯\cdots，2n−12n-1。每一张牌可以移动到后面的任何一个位置，最终不能重叠。换句话说，小可可的最后一张牌可以在后两张牌中选取，倒数第二张排可以在后四张牌中选取，依次类推。
这样我们就会计算答案了——显然每一步都可以贪心。所以你开一个堆，从 nn 到 11，每次往堆里面加入 22 个 aia_i，并且取出堆顶。复杂度 O(mn×nlog⁡n)O(m^n \times n \log n)。
这样也许可以拿到 2424 分？看你常数怎么样了。拿到这档分的小朋友未来很有希望的：你有很强的分析问题的能力，和获得更高的分只差了经典技巧的积累，多做点题就能克服这一关了！
这类问题有一个经典的讨论：“二分”转 0101。
设 fif_i 表示，最终取出的 nn 张牌中，有多少张排的大小 ≥i\ge i。答案显然就是 ∑i=1mfi\sum_{i=1}^m f_i。根据期望的线性性，E(∑i=1mfi)=∑i=1mE(fi)E(\sum_{i=1}^m f_i) = \sum_{i=1}^m E(f_i)，所以你想方设法算出 E(fi)E(f_i)。
可以证明，fif_i 等于：将 ≥i\ge i 的数看做 11，≤i\le i 的数看做 00，执行上面贪心的流程得到的结果。
这么做的好处是什么呢？由于所有数要么是 00 要么是 11，我们只需要关心堆里面有多少个 11，而这样的状态数就比较少，可以进行 DP！（这里有点 DP 套 DP 的感觉了，和去年 T4 很像！）
假设我们需要求 fxf_x。设 dpi,jdp_{i,j} 表示，执行了所有 i0≥ii_0 \ge i 后，堆中有 jj 个 11 的概率。最终状态是 dp1,jdp_{1,j}，表示堆里面还剩了 jj 个 11。这样假设加入了 kk 个 11，小可可就取出了 k−jk-j 个 11。我们的答案是 E(k−j)=E(k)−E(j)E(k-j)=E(k)-E(j)，其中 E(j)=∑j(j−min⁡{j,i−1})dpi,jE(j) = \sum_j (j-\min\{j,i-1\}) dp_{i,j}，E(k)=E(∑i=1n[ai≥x])=∑i=1nE([ai≥x])=∑i=1np(ai≥x)E(k) = E(\sum_{i=1}^n [a_i \ge x]) = \sum_{i=1}^n E([a_i \ge x]) = \sum_{i=1}^n p(a_i \ge x)，其中 pp 表示概率。
dpi,jdp_{i,j} 的转移是容易的，你分类讨论一下 aia_i 和 xx 的关系即可。
复杂度 O(n2m)O(n^2 m)，可以拿到 5252 分。拿到这一档分的小朋友很强大：你有很强的算法功底，和正解只差了高级算法，多学一段时间就可以克服！
给定 xx 做 DP 的时候，[ai≥x][a_i \ge x] 一共有 2n2^n 种可能。每一种可能都有出现的概率 p(A)p(A)，以及贡献 c(A)c(A)。c(A)c(A) 在 AA 确定的时候是一个常数，而 p(A)p(A) 应当是每一位对应概率的乘积。而这个概率要么是常数，要么是关于 xx 的一次函数。所以 p(A)p(A) 是一个关于 xx 的不超过 nn 次多项式。对 2n2^n 种情况求和，还是关于 xx 的不超过 nn 次多项式。
一个值得关注的事情是，设 prei=∑j≤iajpre_i = \sum_{j \le i} a_j。当 x≤preix \le pre_i 时概率是关于 xx 的一次函数，>x> x 时概率是常数。所以本质上要把 xx 分为 nn 段去算，同一段内 p(A)p(A) 是相同的，fx=Z(x)f_x = Z(x) 的这个 ZZ 也是相同的。
所以我们相当于知道了 ZZ，求出 ∑x=prei−1+1preiZ(x)\sum_{x=pre_{i-1}+1}^{pre_i} Z(x)。
所以我们可以设 dpi,jdp_{i,j} 为一个关于 xx 的多项式，记录它的系数。转移是 O(n)O(n) 的，因为要乘上一个一次函数。不同的段对应的其实是 DP 终点不同，发现可以共用同一个 dpi,jdp_{i,j}。然后你就只需要求出：∑x=1nxk\sum_{x=1}^n x^k。这是经典的拉格朗日插值优化问题。
其实你可以直接把 xx 挂进 dpi,jdp_{i,j} 里算的，然后使用拉格朗日插值求出 Z(x)Z(x) 的前缀和。后者是关于 xx 的 n+1n+1 次多项式，需要 n+2n+2 个点值。
我选择了后者，因为它实现起来更加方便。
复杂度 O(n3)O(n^3)。我猜赛时没人过。
所以什么时候我能给科大国创出题啊 /kel
哎拉插常数太大了，拼尽全力卡进了 1 秒。
代码：
CPP
#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=500+10,MOD=1e9+7;
int n,m,a[MAXN],pre[MAXN],inv[MAXN],dp[MAXN][MAXN],E[MAXN][MAXN];
ll qpow(ll base,int p) {
	ll ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
void solve(int v) {
	dp[n+1][0]=1;
	int ad=0;
	roff(i,n,1) {
		ffor(j,0,n-i+1) dp[i][j]=0;
		ffor(j,0,n-i+1) {
			ll p=1ll*(pre[i]-v+1)%MOD*inv[i]%MOD;
			dp[i][j+1]=(dp[i][j+1]+dp[i+1][j]*p)%MOD;
			p=(1-p)%MOD; 
			dp[i][max(0,j-1)]=(dp[i][max(0,j-1)]+dp[i+1][j]*p)%MOD;
		}
		ll p=1ll*(pre[i]-v+1)%MOD*inv[i]%MOD;
		ad=(ad+p)%MOD,E[i][v]=2*ad%MOD;
		ffor(j,0,n-i+1) E[i][v]=(E[i][v]-1ll*dp[i][j]*(j-min(i-1,j)))%MOD;
	}
	return ;
}
int tot;
pair<int,int> vc[MAXN];
inline int lagrange(const int x1,const int x2) {
	int ans=0;
	ffor(id,1,tot) {
		auto pr=vc[id];
		ll mul,mul1=pr.second,mul2=pr.second,div=1;
		ffor(j,1,tot) if(j!=id) {auto npr=vc[j]; mul1=(x1-npr.first)*mul1%MOD,mul2=(x2-npr.first)*mul2%MOD,div=(pr.first-npr.first)*div%MOD;}
		mul=(mul1-mul2)%MOD,mul=mul*qpow(div,MOD-2)%MOD;
		ans=(ans+mul)%MOD;
	}
	return ans;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,n) cin>>a[i],pre[i]=pre[i-1]+a[i];
	ffor(i,1,n) inv[i]=qpow(pre[i],MOD-2);
	ffor(v,1,n+2) solve(v);
	ffor(i,1,n) ffor(j,1,n+2) E[i][j]=(E[i][j]+E[i][j-1])%MOD;
	int ans=0;
	ffor(i,1,n) {
		tot=0;
		ffor(j,1,n+2) vc[++tot]={j,E[i][j]};
		ans=(ans+lagrange(pre[i],pre[i-1]))%MOD;
	}
	cout<<(ans%MOD+MOD)%MOD;
	return 0;
}

评论

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

正在加载评论...