ARC139D

所有数的和可以转化为对于每个 \(1\le i\le m\)，计算有多少个数 \(\ge i\) 即可。
开始时先找到 \(\ge i\) 的左端点，然后考虑这个左端点的移动，先考虑开始时在 \(x\) 右边，那么如果放 \([1,i−1]\)，那么位置不变，如果放 \([i,m]\)，那么就左移动一格。在 \(x\) 左边同理。
那么直接枚举多少次操作使得左端点改变，计算方案数即可。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005, mod = 998244353;
int C[N][N], mul[N][N];

void prework(int n) {
	for (int i = 0; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}
	for (int i = 0; i <= n; ++i) {
		mul[i][0] = 1;
		for (int j = 1; j <= n; ++j) mul[i][j] = 1ll * mul[i][j - 1] * i % mod;
	}
}

int n, m, k, X, ans, cnt[N];

int main() {
	scanf("%d%d%d%d", &n, &m, &k, &X);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), ++cnt[x];
	for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
	prework(2000);
	for (int i = 1; i <= m; ++i) {
		int tot = cnt[i - 1];
		for (int j = 0; j <= k; ++j) {
			int tmp = C[k][j];
			if (tot >= X) tmp = 1ll * tmp * mul[i - 1][k - j] % mod * mul[m - i + 1][j] % mod * min(n - X + 1, n - (tot - j)) % mod;
			else tmp = 1ll * tmp * mul[m - i + 1][k - j] % mod * mul[i - 1][j] % mod * max(n - X + 1, n - (tot + j)) % mod; 
			ans = (ans + tmp) % mod;
		}
	}
	printf("%d", ans);
	return 0;
}