飚速布

2024.10.24 T4

题意

$n$ 个数 $a_1,a_2,a_3,\dots ,a_n$。有 $m$ 轮操作，第 $i$ 轮操作选择恰好 $k$ 个数使它 $+1$。

设 $U=[1,n]\cap \mathbb{N}$，$A$ 为 $U$ 的非空子集。求存在操作方案使得 $\forall i\in A,j\in {\complement }_{U}A$，最终的 $a_i^{\prime }\ge a_j^{\prime }$ 的 $A$ 的个数。

$1\le n,m,k,a_i\le 200$，3s，512MB。

做法

先对 $a$ 从大到小排序。

若 $p=|A|<k$。

枚举被选取的第 $i$ 个作为 $A$ 中最靠后的元素。

那么在 $[1,i-1]$ 中有 $i-p$ 个没有被选择。

对于这些自增操作，先让选了的 $p$ 个自增 $m$ 次，再让 $[i+1,n]$ 中的自增 $m$ 次（不会超过 $a_i+m$）。

如果 $k-p-n+i>0$，也即还有多余的部分需要往前面放，只能在那 $i-p$ 个数里面选。

设这 $i-p$ 个没有被选择的下标的集合为 $S$。

总共还需要增加 $m$ 轮，每轮需要增加 $k-p-n+i$ 次。

注意到，任意时刻，任意未选的数不能超过 $a_i+m$，也就是：

$$\begin{array}{c}\forall j\in S,a_i\le a_j\le a_i+m\end{array}$$

第 $j$ 个的变化空间（至多还能被增加的次数）为 $a_i-a_j+m$。

根据经典结论，这 $m$ 轮操作能够成功当且仅当 ${\sum }_{j\in S}\min (m,a_i-a_j+m)\ge m(k-p-n+i)$。

注意到 $a_i-a_j+m$ 这个数一定不大于 $m$，所以把 $\min$ 化掉：

$$\sum _{j\in S}(a_i-a_j+m)\ge m(k-p-n+i)$$

将 $|S|=i-p$ 带入得：

$$m|S|+\sum _{j\in S}(a_i-a_j)\ge m|S|+m(k-n)$$

整理得：

$$\begin{array}{c}\sum _{j\in S}(a_j-a_i)\le m(n-k)\end{array}$$

此外还有这种情况的大前提 $p<k$，即：

$$\begin{array}{c}|S|>i-k\end{array}$$

发现有这个大前提的限制很难办，考虑正难则反。

用满足 $(1)$ 的集合数量减去不满足 $(2)$ 的集合数量。

注意到：

$$\begin{array}{c}\sum _{j\in S}(a_j-a_i)>m(n-k)\end{array}$$

$a_j-a_i\le m$，所以 $|S|>n-k\ge i-k$，此时天然满足 $(3)$，不需要另外考虑了。

求满足 $(4)$ 式的集合数量直接 01 背包。

void solve1() {for (int i = 1; i <= n; ++i) {memset(f, 0, sizeof(f));int sum = 0, cnt = 0; f[0] = 1;for (int j = i-1; j; --j) {if (a[j] - a[i] > m) break;for (int k = sum; ~k; --k) Fplus(f[k+a[j]-a[i]], f[k]);++cnt, sum += a[j]-a[i];}for (int j = max(0, i-k+1); j <= cnt; ++j) Fplus(ans, C[cnt][j]);for (int j = (n-k)*m+1; j <= sum; ++j) Fplus(ans, mod-f[j]);}
}

另一种情况，设 没选 的 $q$ 个，第 $i$ 个为最大的，每一轮需要选择 $n-k$ 个数并 $-1$。

然后设 $S$ 为 $i$ 后面被选择的数的下标。

推法是一样的，但是这里考虑了恰好 $|A|=k$ 的情况，所以在 $|S|\ge k-i+1$ 的时候，能够取等号。

题目只要求非空子集，没要求非空真子集，所以最后还要加上 $U$ 自身的 $1$。

组合数直接杨辉三角。

$O(n^2\sum a_i)$ 小常数直接冲过。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
const int MAXN = 205;
const int MAXM = 40005;
const int mod = 998244353;template <typename Tp> void read(Tp& res) {char ch; bool op = 0; res = 0;do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');do res = (res<<3)+(res<<1)+(ch&15), ch = getchar(); while (ch >= '0' && ch <= '9');if (op) res = -res;
}template <typename Tp> void write(Tp x) {if (x / 10) write(x / 10);putchar(x % 10 + 48);
}int n, m, k, ans, a[MAXN], f[MAXM];
int C[MAXN][MAXN];inline int fplus(int x, int y) {return x + y >= mod ? x + y - mod : x + y;
}inline int Fplus(int& x, int y) {return x = fplus(x, y);
}void solve1() {for (int i = 1; i <= n; ++i) {memset(f, 0, sizeof(f));int sum = 0, cnt = 0; f[0] = 1;for (int j = i-1; j; --j) {if (a[j] - a[i] > m) break;for (int k = sum; ~k; --k) Fplus(f[k+a[j]-a[i]], f[k]);++cnt, sum += a[j]-a[i];}for (int j = max(0, i-k+1); j <= cnt; ++j) Fplus(ans, C[cnt][j]);for (int j = (n-k)*m+1; j <= sum; ++j) Fplus(ans, mod-f[j]);}
}void solve2() {for (int i = 1; i <= n; ++i) {memset(f, 0, sizeof(f));int sum = 0, cnt = 0; f[0] = 1;for (int j = i+1; j <= n; ++j) {if (a[i] - a[j] > m) break;for (int k = sum; ~k; --k) Fplus(f[k+a[i]-a[j]], f[k]);++cnt, sum += a[i]-a[j]; } for (int j = max(0, k-i+1); j <= cnt; ++j) Fplus(ans, C[cnt][j]);for (int j = k*m+1; j <= sum; ++j) Fplus(ans, mod-f[j]);}
}int main() {#ifndef ONLINE_JUDGEfreopen("speed.in", "r", stdin);freopen("speed.out", "w", stdout);#endifread(n), read(m), read(k);C[0][0] = 1;for (int i = 1; i <= n; ++i) {C[i][0] = 1;for (int j = 1; j <= i; ++j) C[i][j] = fplus(C[i-1][j-1], C[i-1][j]);}for (int i = 1; i <= n; ++i) read(a[i]);sort(a+1, a+n+1, [](int x, int y){return x > y;});ans = 1;solve1(), solve2(); write(ans), putchar('\n');return 0;
}