专栏文章

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

2251Sec
P12251题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip4pzfw
此快照首次捕获于
2025/12/03 06:07
3 个月前
此快照最后确认于
2025/12/03 06:07
3 个月前
查看原文
花了 40mins 过掉这个题。这个题给初中生做真的大丈夫？？？
首先瞪一下对一个序列怎么求答案，你发现就是维护一个小根堆，每次把一个数插入两次，然后弹掉堆顶。最后堆里所有元素的和就是答案。
我们先把 aia_i 做个前缀和，这样比较方便描述。然后我们算方案数，最后除掉 ∏ai\prod a_i 即可。
那么套路地，枚举一个阈值 ww，转 01，设 f(i,j)f(i,j) 代表已经考虑前 ii 次解锁，目前堆里有 jj 个 11 的方案数。这样就做到了 O(n2m)O(n^2m)。不难观察到这是一个以 aia_i 为分段点的 O(n)O(n) 次的分段多项式，容易拉插做到 O(n4)O(n^4)。
但是然后怎么办？这个做法看起来并没有什么优化前途。我们不得不转换视角：我们发现，对于 w>aiw > a_i 的部分，我们的转移非常简单：就是对应项乘上 aia_i。而满足 w>aiw > a_i 的部分是一个前缀——这给了我们一个启示：把 DP 倒过来。
把 DP 的过程看成 DAG 上的游走后，我们当然可以把整个 DAG 的边全部反过来，这样，我们就会先走若干 w≤aiw \le a_i 的边，然后走若干 w>aiw > a_i 的边。前面这一部分不再是一个分段多项式：它整个就是个多项式。而后面这部分的系数我们可以在 DP 外乘上去。这样，我们可以写出如下暴力算法：
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
int n, m, a[505];
ll ans, f[505][505];
void F(int w) {
	memset(f, 0, sizeof(f));
	for (int i = 0; i <= n; i++) f[n][i] = i;
	for (int i = n; i; i--) {
		for (int j = 0; j <= i; j++) f[i][j] %= P;
		for (int j = 0; j < i; j++) {
			f[i - 1][j] += f[i][j] * (w - 1);
			f[i - 1][j] += f[i][j + 2 - (j == i - 1)] * (a[i] - w + 1);
		}
	}
}
ll QPow(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] += a[i - 1];
	for (int i = 1; i <= n; i++) {
		for (int j = a[i - 1] + 1; j <= a[i]; j++) {
			F(j);
			ll t = f[i - 1][0];
			for (int k = 1; k < i; k++) t = t * a[k] % P;
			ans += t;
		}
	}
	ans %= P;
	for (int i = 1; i <= n; i++) ans = ans * QPow(a[i], P - 2) % P;
	printf("%lld\n", ans);
	return 0;
}
接下来的部分就顺理成章了。我们对这个 DP 的前缀和进行插值即可。注意前缀和是 (n+1)(n+1) 次而不是 nn 次。复杂度 O(n3)O(n^3)。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 501, P = 1e9 + 7;
int n, m, a[505];
ll ans, f[505][505], g[505][505];
void F(int w) {
	memset(f, 0, sizeof(f));
	for (int i = 0; i <= n; i++) f[n][i] = i;
	for (int i = n; i; i--) {
		for (int j = 0; j <= i; j++) f[i][j] %= P;
		for (int j = 0; j < i; j++) {
			f[i - 1][j] += f[i][j] * (w - 1);
			f[i - 1][j] += f[i][j + 2 - (j == i - 1)] * (a[i] - w + 1);
		}
	}
	for (int i = 0; i <= n; i++) g[i][w] = f[i][0] % P;
}
ll QPow(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
	return res;
}
ll Calc(int u, int x) {
	ll res = 0;
	for (int i = 0; i <= N; i++) {
		ll a = 1, b = 1;
		for (int j = 0; j <= N; j++) {
			if (i == j) continue;
			a = a * (x - j) % P;
			b = b * (i - j) % P;
		}
		res += g[u][i] * a % P * QPow(b, P - 2) % P;
	}
	return (res % P + P) % P;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] += a[i - 1];
	for (int i = 0; i <= N; i++) F(i);
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= N; j++) (g[i][j] += g[i][j - 1]) %= P;
	}
	for (int i = 1; i <= n; i++) {
		ll t = Calc(i - 1, a[i]) - Calc(i - 1, a[i - 1]) + P;
		for (int k = 1; k < i; k++) t = t * a[k] % P;
		ans += t;
	}
	ans %= P;
	for (int i = 1; i <= n; i++) ans = ans * QPow(a[i], P - 2) % P;
	printf("%lld\n", ans);
	return 0;
}

评论

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

正在加载评论...