首页 > 其他分享 >CF1188C

CF1188C

时间:2022-10-16 16:33:16浏览次数:62  
标签:int 个数 枚举 CF1188C 答案 mathcal mod

又一次错过了单杀 *2500 的机会,不知道该说什么了。。

先把 \(a\) 排序,不会影响答案。

考虑枚举答案 \(v\),计算有多少种选择子序列的方法使得答案为 \(v\)。

这不太好做,考虑放宽限制,计算有多少种选择子序列的方法使得答案不小于 \(v\),最后把方案数加起来就好了。

设 \(f_{i,j}\) 表示从前 \(i\) 个数选择 \(j\) 个数,并且强制选第 \(i\) 个数的方案数。

枚举上一个数选的是什么,转移为 \(f_{i,j}=\sum\limits_{a_i-a_k\ge v}{f_{k,j-1}}\)。

直接转移是 \(\mathcal O(n^2k)\) 的,双指针+前缀和优化后可以做到 \(\mathcal O(nk)\)。

但是外面还有枚举 \(v\) 的复杂度啊。(我就是卡在了这里)

但是注意到,答案最多不会超过 \(\frac{\max a_i}{k-1}\),因为 \(k\) 个数有 \(k-1\) 个空。

所以总的复杂度为 \(\mathcal O(\frac{v}{k}nk)=\mathcal O(nv)\),可以通过。

具体细节看代码。

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005, M = 100005, mod = 998244353, inf = 0x3f3f3f3f;
int n, k;
int a[N];
int f[N][N], sum[N][N];
int ans;

void add(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1), a[0] = -inf;
	for (int v = 1; v * (k - 1) <= 100000; ++v) {
		int p = 0, cur = 0; f[0][0] = sum[0][0] = 1;
		for (int i = 1; i <= n; ++i) {
			while (a[i] - a[p] >= v) ++p;
			for (int j = 0; j <= k; ++j) {
				if (j) f[i][j] = sum[p - 1][j - 1];
				sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
			}
			add(cur, f[i][k]);
		}
		add(ans, cur);
	}
	printf("%d", ans);
	return 0;
}

标签:int,个数,枚举,CF1188C,答案,mathcal,mod
From: https://www.cnblogs.com/Kobe303/p/16796467.html

相关文章