是一道不错的计数。
考察合法序列的形态,容易发现:
- 不能出现两个 \(< \frac{k}{2}\) 的数相邻;
- 如果 \(x < \frac{k}{2}, y \ge \frac{k}{2}\),那么 \(|y - \frac{k}{2}| \ge |x - \frac{k}{2}|\)。
考虑不直接排列,而是按照一定的顺序插入。考虑按照 \(|x - \frac{k}{2}|\) 从大到小插入,并且如果 \(|x - \frac{k}{2}|\) 相同,那么就让 \(\ge \frac{k}{2}\) 的数先插入,这样能保证不会出现第二种不合法情况。因为题目不区分相同的数,于是把所有相同的数放一起考虑。
于是只用限制第一个不合法情况。维护一个可用位置数 \(s\),然后:
- 遇到 \(x < \frac{k}{2}\),出现次数为 \(y\),那我们有 \(\binom{s}{y}\) 种方案插入,并且可用位置数减去 \(y\)(之后不能在它们两侧放数了);
- 遇到 \(x \ge \frac{k}{2}\),出现次数为 \(y\),这个插入的方案数相当于,把这 \(y\) 个数划分成 \(s\) 段,把这 \(s\) 段依次插入,允许有空段。这个用插板法可得方案数为 \(\binom{s + y - 1}{s - 1}\),并且可用位置数加上 \(y\)。
最后由乘法原理把每一步的方案数乘起来就是最终答案。
时间复杂度 \(O(n \log n)\),瓶颈在排序。
code
// Problem: E - ≥ K
// Contest: AtCoder - AtCoder Regular Contest 148
// URL: https://atcoder.jp/contests/arc148/tasks/arc148_e
// Memory Limit: 1024 MB
// Time Limit: 2000 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 = 200100;
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, m, a[maxn], fac[maxn], ifac[maxn], tot;
pii b[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;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
map<ll, ll> mp;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
++mp[a[i]];
}
for (pii p : mp) {
b[++tot] = p;
}
fac[0] = 1;
for (int i = 1; i <= n; ++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;
}
sort(b + 1, b + tot + 1, [&](pii a, pii b) {
return abs(a.fst * 2 - m) > abs(b.fst * 2 - m) || (abs(a.fst * 2 - m) == abs(b.fst * 2 - m) && a.fst * 2 > m);
});
ll ans = 1, s = 1;
for (int i = 1; i <= tot; ++i) {
if (b[i].fst * 2 < m) {
ans = ans * C(s, b[i].scd) % mod;
s -= b[i].scd;
} else {
ans = ans * C(s + b[i].scd - 1, s - 1) % mod;
s += b[i].scd;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest 148atcoder regular contest 148 beginner atcoder contest 148 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder