P12251 [科大国创杯初中组 2025] 抽卡题解

场外 VP，小朋友太惨了。

$O(n^2m)$ 做法

非常经典地，将

\ge x

的数视为

1

，其余视为

0

，这样就将贡献拆掉，问题简化。

与马队和 asdfz 的诸位大佬不同的是，我的朴素 DP 是正着做的（这样似乎更易理解和记答案？）。

设

f_{i,j}

表示前

2i

个数中合法选出

j

个

1

的概率，

p_i=\sum_{k=1}^{i} a_k

。

则

f_{i,j}=f_{i-1,j-2}\cdot (1-\frac{x-1}{p_i}) +f_{i-1,j}\cdot \frac{x-1}{p_i}

，其中

j\le i,p_i\ge x

。

易知对答案的贡献为

\sum j f_{n,j}

。

代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const long long mod=1000000007;
long long f[N][2],inv,ans;
int n,m,s,a[N],p[N];
long long qpow(long long x,int y)
{
	long long z=1;
	while(y)
	{
		if(y&1)
			z=z*x%mod;
		x=x*x%mod,y>>=1;
	}
	return z;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	int cur;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>a[i],p[i]=a[i]+p[i-1];
	for(int t=1;t<=n;s+=a[t],++t)
	{
		for(int x=s+1;x<=s+a[t];++x)
		{
			memset(f,0,sizeof f),f[0][0]=1,cur=1;
			for(int i=t;i<=n;++i,cur^=1)
			{
				inv=(p[i]-x+1)*qpow(p[i],mod-2)%mod;
				for(int j=0;j<=i;++j)
				{
					f[j][cur]=f[j][!cur]*(1-inv)%mod;
					if(j>=2)
						f[j][cur]=(f[j][cur]+f[j-2][!cur]*inv)%mod;
				}
				f[i][cur]=(f[i][cur]+f[i-1][!cur]*inv)%mod;
			}
			for(int j=1;j<=n;++j)
				ans=(ans+j*f[j][!cur])%mod;
		}
	}
	cout<<(ans+mod)%mod;
	return 0;
}

$O(n^3)$ 做法

上述做法大约只能用拉插优化到

O(n^4)

，原因在于未能有效利用之前的信息。

要作一个转化，合法相当于后

2i

个数至少取

i

个，即在每个

2j+1

处取局部最优值，再拆一下期望，具体见 Purslane 的题解。

下面就与他们的 DP 式子一样了，处理时我是记录下降幂的系数，使用一些有限微积分的技巧求和，即：

\sum_a^{b-1} x^{\underline{n}}=\frac{b^{\underline{n+1}}-a^{\underline{n+1}}}{n+1}

。

代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const long long mod=1000000007;
long long q[N][2],invv[N],ans;
int n,m,s,a[N],p[N];
struct poly{
	long long a[N];					//下降幂 
	void operator+=(const poly &x)
	{
		for(int i=0;i<=n;++i)
			a[i]=(a[i]+x.a[i])%mod;
	}
	poly operator*(const long long x)
	{
		poly y;
		for(int i=0;i<=n;++i)
			y.a[i]=a[i]*x%mod;
		return y;
	}
}f[N][2],A;
poly times(const poly &x,const long long a,const long long b)
{
	poly y;
	y.a[0]=x.a[0]*b%mod*a%mod;
	for(int i=1;i<=n;++i)
		y.a[i]=(x.a[i-1]+x.a[i]*(b+i))%mod*a%mod;
	return y;
}
long long qpow(long long x,int y)
{
	long long z=1;
	while(y)
	{
		if(y&1)
			z=z*x%mod;
		x=x*x%mod,y>>=1;
	}
	return z;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	int cur=1;
	long long inv,u=0,v=0;
	cin>>n>>m;
	invv[0]=1;
	for(int i=1;i<=n;++i)
		cin>>a[i],p[i]=a[i]+p[i-1],invv[i]=qpow(i+1,mod-2);
	f[0][0].a[0]=1;
	for(int i=n;i>=1;--i,cur^=1)
	{
		memset(A.a,0,sizeof A.a),inv=qpow(p[i],mod-2)%mod,u+=2,v=(v-2*inv)%mod;
		for(int j=n-i+1;j>=0;--j)
		{
			f[j][cur]=times(f[j+1][!cur],inv,0);
			if(j==0)
				f[j][cur]+=times(f[j][!cur],inv,0);
			else
				f[j][cur]+=times(f[j-1][!cur],-inv,-p[i]);
		}
		for(int j=0;j<=n;++j)
			A+=f[j][cur]*(-max(j-i+1,0));
		A.a[0]+=u,A.a[1]+=v;
		q[0][0]=q[0][1]=1;
		for(int j=1;j<=n+1;++j)
			q[j][0]=q[j-1][0]*(p[i]+1-j)%mod,q[j][1]=q[j-1][1]*(p[i-1]+1-j)%mod;
		for(int j=0;j<=n;++j)
			ans+=A.a[j]*invv[j]%mod*(q[j+1][0]-q[j+1][1])%mod;
		ans%=mod;
	}
	cout<<(ans+mod)%mod;
	return 0;
}

所以什么时候我能给科大国创出题啊。

本题解与笔者的代码在伟大的 Purslane 的指导下完成，让我们一起拜谢马队，祝他在绍兴 Au。

P12251 [科大国创杯初中组 2025] 抽卡题解

文章操作

$O(n^2m)$ 做法

$O(n^3)$ 做法

相关推荐

评论

P12251 [科大国创杯初中组 2025] 抽卡题解

文章操作

O(n2m)O(n^2m)O(n2m) 做法

O(n3)O(n^3)O(n3) 做法

相关推荐

评论

$O(n^2m)$ 做法

$O(n^3)$ 做法