飚速布
2024.10.24 T4
题意
n n n 个数 a 1 , a 2 , a 3 , … , a n a_1, a_2, a_3, \dots, a_n a1,a2,a3,…,an。有 m m m 轮操作,第 i i i 轮操作选择恰好 k k k 个数使它 + 1 +1 +1。
设 U = [ 1 , n ] ∩ N U = [1, n] \cap \mathbb{N} U=[1,n]∩N, A A A 为 U U U 的非空子集。求存在操作方案使得 ∀ i ∈ A , j ∈ ∁ U A \forall i \in A, j \in \complement_U A ∀i∈A,j∈∁UA,最终的 a i ′ ≥ a j ′ a_i' \ge a_j' ai′≥aj′ 的 A A A 的个数。
1 ≤ n , m , k , a i ≤ 200 1 \le n, m, k, a_i \le 200 1≤n,m,k,ai≤200,3s,512MB。
做法
先对 a a a 从大到小排序。
若 p = ∣ A ∣ < k p = |A| < k p=∣A∣<k。
枚举被选取的第 i i i 个作为 A A A 中最靠后的元素。
那么在 [ 1 , i − 1 ] [1, i-1] [1,i−1] 中有 i − p i-p i−p 个没有被选择。
对于这些自增操作,先让选了的 p p p 个自增 m m m 次,再让 [ i + 1 , n ] [i+1, n] [i+1,n] 中的自增 m m m 次(不会超过 a i + m a_i+m ai+m)。
如果 k − p − n + i > 0 k - p - n + i > 0 k−p−n+i>0,也即还有多余的部分需要往前面放,只能在那 i − p i-p i−p 个数里面选。
设这 i − p i-p i−p 个没有被选择的下标的集合为 S S S。
总共还需要增加 m m m 轮,每轮需要增加 k − p − n + i k-p-n+i k−p−n+i 次。
注意到,任意时刻,任意未选的数不能超过 a i + m a_i+m ai+m,也就是:
∀ j ∈ S , a i ≤ a j ≤ a i + m \begin{equation} \forall j \in S, a_i \le a_j \le a_i+m \end{equation} ∀j∈S,ai≤aj≤ai+m
第 j j j 个的变化空间(至多还能被增加的次数)为 a i − a j + m a_i - a_j + m ai−aj+m。
根据经典结论,这 m m m 轮操作能够成功当且仅当 ∑ j ∈ S min ( m , a i − a j + m ) ≥ m ( k − p − n + i ) \sum_{j \in S} \min(m, a_i - a_j + m) \ge m(k-p-n+i) ∑j∈Smin(m,ai−aj+m)≥m(k−p−n+i)。
注意到 a i − a j + m a_i-a_j+m ai−aj+m 这个数一定不大于 m m m,所以把 min \min min 化掉:
∑ j ∈ S ( a i − a j + m ) ≥ m ( k − p − n + i ) \sum_{j \in S} (a_i - a_j + m) \ge m(k-p-n+i) j∈S∑(ai−aj+m)≥m(k−p−n+i)
将 ∣ S ∣ = i − p |S| = i - p ∣S∣=i−p 带入得:
m ∣ S ∣ + ∑ j ∈ S ( a i − a j ) ≥ m ∣ S ∣ + m ( k − n ) m|S| + \sum_{j \in S} (a_i - a_j) \ge m|S| + m(k-n) m∣S∣+j∈S∑(ai−aj)≥m∣S∣+m(k−n)
整理得:
∑ j ∈ S ( a j − a i ) ≤ m ( n − k ) \begin{equation} \sum_{j \in S} (a_j - a_i) \le m(n-k) \end{equation} j∈S∑(aj−ai)≤m(n−k)
此外还有这种情况的大前提 p < k p < k p<k,即:
∣ S ∣ > i − k \begin{equation} |S| > i - k \end{equation} ∣S∣>i−k
发现有这个大前提的限制很难办,考虑正难则反。
用满足 ( 1 ) (1) (1) 的集合数量减去不满足 ( 2 ) (2) (2) 的集合数量。
注意到:
∑ j ∈ S ( a j − a i ) > m ( n − k ) \begin{equation} \sum_{j \in S} (a_j - a_i) > m(n-k) \end{equation} j∈S∑(aj−ai)>m(n−k)
a j − a i ≤ m a_j - a_i \le m aj−ai≤m,所以 ∣ S ∣ > n − k ≥ i − k |S| > n - k \ge i - k ∣S∣>n−k≥i−k,此时天然满足 ( 3 ) (3) (3),不需要另外考虑了。
求满足 ( 4 ) (4) (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 q q 个,第 i i i 个为最大的,每一轮需要选择 n − k n - k n−k 个数并 − 1 -1 −1。
然后设 S S S 为 i i i 后面被选择的数的下标。
推法是一样的,但是这里考虑了恰好 ∣ A ∣ = k |A| = k ∣A∣=k 的情况,所以在 ∣ S ∣ ≥ k − i + 1 |S| \ge k - i + 1 ∣S∣≥k−i+1 的时候,能够取等号。
题目只要求非空子集,没要求非空真子集,所以最后还要加上 U U U 自身的 1 1 1。
组合数直接杨辉三角。
O ( n 2 ∑ a i ) O(n^2\sum a_i) O(n2∑ai) 小常数直接冲过。
代码
#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;
}