完全没有思路。但是其实不难的。
设 \(d_i\) 为 \(i\) 在 \(B\) 中的出现次数,题目要求:
- \(\forall i \in [1, n], d_i \le A_i\);
- 对于位置 \(i\),\(d_j \le A_i\) 的数 \(j\) 可以被放到 \(B_i\)。
考虑按照 \(d_i\) 从大到小 dp。设 \(f_{i, j, k}\) 为,考虑到出现次数 \(\ge i\) 的数,这些数一共有 \(j\) 个,总共出现了 \(k\) 次。
设 \(C_i = \sum\limits_{j = 1}^n [A_j \ge i]\)。\(f_{i + 1} \to f_i\) 时,考虑枚举 \(x\) 个数出现了 \(i\) 次,那么这 \(x\) 个数有 \(\binom{C_i - j}{x}\) 种方案被确定。要把它们填进 \(B\) 中,有 \(\frac{(C_i - k)!}{(\prod\limits_{y = 1}^x i!) \times (C_i - k - ix)}\) 种方案(其实是一个多重组合数)。那么转移式子就是:
\[f_{i, j + x, k + ix} \gets f_{i + 1, j, k} \times \binom{C_i - j}{x} \times \frac{(C_i - k)!}{(\prod\limits_{y = 1}^x i!) \times (C_i - k - ix)}
\]
注意到 \(j\) 和 \(x\) 的上界最大是 \(\left\lfloor\frac{n}{i}\right\rfloor\) 的,所以时间复杂度其实是 \(O(n^3)\)。
code
// Problem: E - Strange Constraints
// Contest: AtCoder - AtCoder Regular Contest 162
// URL: https://atcoder.jp/contests/arc162/tasks/arc162_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 510;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, a[maxn], b[maxn], fac[maxn], ifac[maxn];
int f[maxn][maxn][maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
inline void upd(int &x, int y) {
x += y;
(x >= mod) && (x -= mod);
}
void solve() {
scanf("%lld", &n);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
++b[a[i]];
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
for (int i = n; i; --i) {
b[i] += b[i + 1];
}
f[n + 1][0][0] = 1;
for (int i = n; i; --i) {
for (int j = 0; (i + 1) * j <= n && j <= b[i + 1]; ++j) {
for (int k = 0; k <= b[i + 1]; ++k) {
if (!f[i + 1][j][k]) {
continue;
}
ll pw = 1;
for (int x = 0; j + x <= n && k + i * x <= b[i]; ++x) {
upd(f[i][j + x][k + i * x], f[i + 1][j][k] * C(b[i] - j, x) % mod * fac[b[i] - k] % mod * ifac[b[i] - k - i * x] % mod * pw % mod);
pw = pw * ifac[i] % mod;
}
}
}
}
int ans = 0;
for (int i = 0; i <= b[1]; ++i) {
upd(ans, f[1][i][n]);
}
printf("%d\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Constraints AtCoder Regular Contest Strangeconstraints atcoder regular contest constraints atcoder contest square atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder