【集训04】比赛题解1006

```cpp
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
int main(){
	while(1){
		system("data.exe");//输出数据
		system("baoli.exe");//输出暴力的答案
		system("zhengjie.exe");//输出正解的答案
		if(system("fc baoli.out zhengjie.out")){
			printf("WA\n");//找到hack数据，暂停一下
			Sleep(100000);
		}
		else printf("AC\n");
	}
	return 0;
}
```

#include <bits/stdc++.h>
using namespace std;
#define bywuting ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

queue<int> q[200100];
int pre[200200], nxt[200200], a[200200], n, cnt;

int main() {
	bywuting
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n;) { //处理分块的队列
		int j = i;
		while (j <= n && a[j] == a[i])
			++j;
		++cnt;
		for (int k = i; k < j; k++)
			q[cnt].push(k);
		i = j;
	}
	for (int i = 1; i <= cnt; i++) {
		pre[i] = i - 1;
		nxt[i - 1] = i;
	}
	nxt[cnt] = 0;
	pre[0] = cnt;
	while (nxt[0] != 0) {
		for (int i = nxt[0]; i != 0; i = nxt[i]) { //输出一轮
			cout << q[i].front() << " ";
			q[i].pop();
		}
		int i = nxt[0]; //清理一轮，注意head0不去动他
		while (i != 0) {
			int nx = nxt[i];
			if (q[i].empty()) {
				int l = pre[i], r = nxt[i];
				if (l == 0)
					nxt[0] = r, pre[r] = 0;
				else if (r == 0)
					nxt[l] = 0, pre[0] = l;
				else
					nxt[l] = r, pre[r] = l;
				i = r;
				continue;
			}
			int l = pre[i];
			if (l != 0 && q[l].size() && a[q[l].front()] == a[q[i].front()]) {
				while (!q[i].empty()) {
					q[l].push(q[i].front());
					q[i].pop();
				}
				int r = nxt[i];
				nxt[l] = r;
				if (r != 0)
					pre[r] = l;
				else
					pre[0] = l;
				i = r;
				continue;
			}
			i = nx;
		}
		cout << "\n";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
static const int MOD = 998244353;
static const int MAXN = 5005;
static const int MAXK = 105;   
static const int MAXS = 5005; 
int n, k;
int a[MAXN];
int pre[MAXN];                 
static int dp[MAXK][MAXS]; 
static int S[MAXS];            
static int Cmb[MAXN][MAXK];  
int main() {
    if (scanf("%d %d", &n, &k) != 2) return 0;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int maxA = a[n];
    for (int i = 0; i <= n; ++i) {
        Cmb[i][0] = 1;
        int up = min(k - 1, i);
        for (int c = 1; c <= up; ++c) {
            long long v = Cmb[i - 1][c - 1];
            if (c <= i - 1) v += Cmb[i - 1][c];
            Cmb[i][c] = (int)(v % MOD);
        }
    }
    for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];

    dp[0][0] = 1;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int mx = a[i], v = a[i];
			 if (i >= 3) {
            int cap = min(k - 1, i - 1);
            long long combos = 0;
            for (int c = 2; c <= cap; ++c) {
                combos += Cmb[i - 1][c];
                if (combos >= (long long)MOD * MOD) combos %= MOD;
            }
            combos %= MOD;
            long long bad = 0;
            for (int t = 0; t <= mx; ++t) {
                bad += S[t];
                if (bad >= (long long)MOD * MOD) bad %= MOD;
            }
            bad %= MOD;
            ans += combos - bad;
            ans %= MOD;
            if (ans < 0) ans += MOD;
        }
        int cmax = min(k - 2, i - 1);
        for (int c = cmax; c >= 0; --c) {
            int lo = pre[c];
            int top = pre[i - 1] - (i - 1 > c ? pre[i - 1 - c] : 0);
            int hi = min(maxA - v, top);
            if (lo > hi) continue;
            int *dpc = dp[c], *dpn = dp[c + 1];
            for (int j = hi; j >= lo; --j) {
                int val = dpc[j];
                if (!val) continue;
                int &ref = dpn[j + v];
                ref += val;
                if (ref >= MOD) ref -= MOD;
                if (c >= 1) {   
                    int &sr = S[j + v];
                    sr += val;
                    if (sr >= MOD) sr -= MOD;
                }
            }
        }
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}