題意

給定長度為 \(n\) 的序列 \(a\) 和一個數 \(X\)，求有多少種 \(a\) 的重排 \(b\) 使得 \(\sum\limits_{i=1}^n\max(b_i-i+1,0)\leq X\)。\(1\leq n\leq 100\)，\(1\leq a_i,X\leq 10^9\)。

題解

你說得對，但我怎么見過這個 trick？見過了怎么還做不出來呢？

首先考慮把 \(\sum\) 里面的式子寫成更喜聞樂見的形式，注意到 \(\max(b_i-(i-1),0)+\min(b_i,i-1)=b_i\)，于是我們設 \(S=\sum\limits_{i=1}^na_i,X'=S-X\)，把原題條件轉化為 \(\sum\limits_{i=1}^n\min(b_i,i-1)\geq X'\)。

顯然 \(0\leq \sum\limits_{i=1}^n\min(b_i,i-1)\leq \sum\limits_{i=0}^{n-1}i=\dfrac{n(n-1)}{2}\)，因此若 \(X'>\dfrac{n(n-1)}{2}\) 則無解，若 \(X'<0\) 則答案為 \(n!\)。這樣 \(X'\) 就被限制到了 \(\mathcal{O}(n^2)\) 量級。

看到形如 \(\sum\min(x_i,y_i)\) 的式子，想到將其轉化為匹配問題的 trick。具體來說，我們把 \(a_1,\cdots,a_n\) 視作左部點，\(0,\cdots,n-1\) 視作右部點，把這 \(2n\) 個點放一起按權值從大到小排序。從左往右考慮每個點 \(i\)，那么我們的決策就是，要么把 \(i\) 和前面某個尚未匹配的不同類型的點 \(j\) 匹配，造成 \(v_i\) 的貢獻，要么留著不匹配，等后面的點來匹配它。

容易想到對這個過程 DP。令 \(f_{i,j,k,s}\) 表示考慮前 \(i\) 個數，有 \(j\) 個左部點尚未匹配，有 \(k\) 個右部點尚未匹配，當前匹配的權值和為 \(s\) 的方案數。考慮轉移，不妨假設第 \(i\) 個點是左部點，右部點的情況類似。討論這個點是否和前面的點匹配：

• 第 \(i\) 個點不匹配：\(f_{i,j,k,s}\leftarrow f_{i,j,k,s}+f_{i-1,j-1,k,s}\)。
• 第 \(i\) 個點和前面的點匹配：此時 \(1\sim i-1\) 中有 \(k+1\) 個右部點，可以任選一個和當前點匹配，于是 \(f_{i,j,k,s}\leftarrow f_{i,j,k,s}+(k+1)f_{i-1,j,k+1,s-v_i}\)。

\(s=\mathcal{O}(n^2)\)，這樣我們就得到了 \(\mathcal{O}(n^5)\) 的做法。

考慮優化。設 \(L_i,R_i\) 分別表示前 \(i\) 個點中左部點、右部點的數量。可以發現，我們能由 \(i,j\) 計算出 \(k\)：前 \(i\) 個點中有 \(j\) 個未匹配的左部點，也就會有 \(L_i-j\) 組左右部點的匹配，于是就有 \(R_i-L_i+j\) 個未匹配的右部點。因此我們的 DP 狀態可以簡化成 \(f_{i,j,s}\)，時間復雜度優化至 \(\mathcal{O}(n^4)\)，可以通過本題。

代碼

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 101, MOD = 998244353;

template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }
inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + MOD : x; }
inline void cadd(int &x, int y) { x += y, x < MOD || (x -= MOD); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += MOD); }

int n, ans, a[N], f[N << 1][N << 1][N * (N - 1) / 2], cnt[N << 1][2];
ll S, X;
pii p[N << 1];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> X;
	for (int i = 1; i <= n; ++i) cin >> a[i], S += a[i];
	X = S - X;
	if (X > n * (n - 1) / 2) return cout << "0", 0;
	if (X < 0) {
		int fc = 1;
		for (int i = 1; i <= n; ++i) fc = (ll)fc * i % MOD;
		return cout << fc, 0;
	}
	for (int i = 1; i <= n; ++i) p[i] = {a[i], 0}, p[i + n] = {i - 1, 1};
	sort(p + 1, p + (n << 1) + 1, greater<>());
	for (int i = 1; i <= n << 1; ++i) cnt[i][0] = cnt[i - 1][0] + !p[i].second, cnt[i][1] = cnt[i - 1][1] + p[i].second;
	f[0][0][0] = 1;
	int u = n * (n - 1) / 2;
	for (int i = 1; i <= n << 1; ++i) for (int j = 0; j <= cnt[i][0]; ++j) {
		int k = cnt[i][1] - cnt[i][0] + j;
		if (k < 0 || k > cnt[i][1]) continue;
		for (int s = 0; s <= u; ++s) {
			if (p[i].second) {
				if (p[i].first <= s) cadd(f[i][j][s], (ll)(j + 1) * f[i - 1][j + 1][s - p[i].first] % MOD);
				if (k) cadd(f[i][j][s], f[i - 1][j][s]);
			} else {
				if (p[i].first <= s) cadd(f[i][j][s], (ll)(k + 1) * f[i - 1][j][s - p[i].first] % MOD);
				if (j) cadd(f[i][j][s], f[i - 1][j - 1][s]);
			}
		}
	}
	for (int s = X; s <= u; ++s) cadd(ans, f[n << 1][0][s]);
	cout << ans;
	return 0;
}