题面

题意

给出一个长度为 $n$ 的序列 $S$，$S$ 单调递增，问你有多少个序列 $T$ 以满足下列条件：

1. $T$ 是 $S$ 的一个排列。
2. $\sum_{i=1}^{n} \min(S_i,~T_i) = k$

$1 \le k \le 2500,~1 \le n \le 50,~1 \le S_i \le 50$

分析

我们发现 $k$ 的值非常小，所以我们考虑使用类似背包的方法考虑每一个 $S_i$ 和 $T_i$ 对总答案的贡献。

由于 $S$ 单调递增所以 $S$ 中的数互不相同，因此我们可以直接考虑分类讨论值 $S_i$ 在 $T$ 中的位置，令 $T_j = S_i$ 则：

1. 若 $j < i$，$S_j < S_i = T_j$，因此 $S_i$ 对答案产生 $0$ 的贡献。
2. 若 $j = i$，$S_j = S_i = T_j$，因此 $S_i$ 对答案产生 $S_i$ 的贡献。
3. 若 $j > i$，$S_j > S_i = T_j$，因此 $S_i$ 对答案产生 $S_i$ 的贡献。

计算答案的问题解决了，但是如何记录 $S_i$ 在 $T$ 中的位置？显然我们只关心 $j$ 与 $i$ 的大小关系，并不关心 $j$ 的具体值。因此我们只需要知道有多少中情况满足 $j < i$，$j = i$，$j > i$ 即可。

考虑使用 DP 解决此问题，$f[i][j][k]$ 表示已考虑 $S_1 \sim S_i$ 部分，$T_1 \sim T_i$ 中有 $j$ 个位置尚未确定值，且 $S_1 \sim S_i$ 部分对总答案的贡献为 $k$ 的方案数。转移时枚举 $j$ 与 $i$ 的大小关系和 $T_i$ 是否确定值即可。$T_i$ 不确定值时即意味 $T_i$ 将用 $> S_i$ 的数填充，$T_i$ 确定值时即意味 $T_i$ 将用 $\le S_i$ 的数填充。

具体转移见代码，建议手画几个图细心分析。

代码

View on GitHub

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 * @brief
 *      My solution: https://macesuted.cn/article/htr003d/
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {
#define SIZE (1 << 20)
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int f, qr;
inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
inline void putch(char x) {
    *oS++ = x;
    if (oS == oT) flush();
    return;
}
string getstr(void) {
    queue<char> que;
    char c = getch();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
    while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) que.push(c), c = getch();
    string s;
    s.resize(que.size());
    for (register int i = 0; i < (int)s.size(); i++) s[i] = que.front(), que.pop();
    return s;
}
void putstr(string str, int begin = 0, int end = -1) {
    if (end == -1) end = str.size();
    for (register int i = begin; i < end; i++) putch(str[i]);
    return;
}
template <typename T>
inline T read() {
    register T x = 0;
    for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
    return x * f;
}
template <typename T>
inline void write(const T& t) {
    register T x = t;
    if (!x) putch('0');
    if (x < 0) putch('-'), x = -x;
    while (x) qu[++qr] = x % 10 + '0', x /= 10;
    while (qr) putch(qu[qr--]);
    return;
}
struct Flusher_ {
    ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 55
#define maxk 2505
#define mod 1000000009

int a[maxn];
long long f[maxn][maxn][maxk];

long long Mod(long long& a) { return a = (a >= mod ? a - mod : a); }

int main() {
    int n = read<int>(), K = read<int>();
    for (register int i = 1; i <= n; i++) a[i] = read<int>();
    f[0][0][0] = 1;
    for (register int i = 0; i < n; i++)
        for (register int j = 0; j <= i; j++)
            for (register int k = 0; k <= K; k++)
                if (f[i][j][k]) {
                    // T[j] 向前匹配，S[j] 留空
                    if (j && k + a[i + 1] <= K) Mod(f[i + 1][j][k + a[i + 1]] += 1LL * j * f[i][j][k] % mod);
                    // T[j] 向后匹配，S[j] 留空
                    if (k + 2 * a[i + 1] <= K) Mod(f[i + 1][j + 1][k + 2 * a[i + 1]] += f[i][j][k]);
                    // T[j] 向前匹配，S[j] 填充
                    if (j) Mod(f[i + 1][j - 1][k] += 1LL * j * j % mod * f[i][j][k] % mod);
                    // T[j] = S[j]
                    if (k + a[i + 1] <= K) Mod(f[i + 1][j][k + a[i + 1]] += f[i][j][k]);
                    // T[j] 向后匹配，S[j] 填充
                    if (j && k + a[i + 1] <= K) Mod(f[i + 1][j][k + a[i + 1]] += 1LL * j * f[i][j][k] % mod);
                }
    write(f[n][0][K]), putch('\n');
    return 0;
}