下文令 \(n\) 为原题中的 \(K\)，\(m\) 为原题中的 \(N\)。
首先概率转方案数，最后除 \(2^{nm}\) 即可。
考虑一个指数级暴力：枚举每个 bot 的终点 \(y_i\)（因为存在不能相交的限制，需要满足 \(y_1 < y_2 < \cdots < y_n\)），相当于为每个 bot 选一个 \((0, x_i) \to (m, y_i)\) 的路径（\((s, x)\) 表示第 \(s\) 秒坐标为 \(x\)），满足路径两两不交。
立刻想到 LGV 引理，于是有下面的式子：
\[ans = \sum\limits_{p} (-1)^{\sigma(p)} \prod\limits_{i = 1}^n e(i, p_i) \]其中 \(\sigma(p)\) 为 \(p\) 逆序对数，\(e(i, j)\) 为从 \((0, x_i)\) 到 \((m, y_i)\) 的方案数。\(m\) 步中选 \(y_j - x_i\) 步往前走，可得 \(e(i, j) = \binom{m}{y_j - x_i}\)。
这个式子也可以用容斥来解释。如果两个 bot 的路径有交点，那么找到最后一个交点，交换它们之后的路径，发现方案数和原来相同，且 \(\sigma(p)\) 奇偶性一定改变。
也就是说我们现在需要知道所有 \(x_i\) 对应的 \(y_{p_i}\)。考虑从小到大枚举 \(y\) 做一个 dp，\(f_{S, k}\) 为当前已经确定 \(y_{p_i}\) 的所有 \(i\) 的集合为 \(S\)，当前已经确定的所有 \(y_{p_i}\) 都 \(\le k\)，上述式子的值。
转移枚举是否存在一个 \(i\) 使得 \(y_{p_i} = k\)。
- 若不存在，则 \(f_{S, k} \gets f_{S, k - 1}\)。
- 若存在，则枚举这个 \(i\)。拆贡献，把 \((-1)^{\sigma(p)}\) 分摊到每个 \(p_i\)。由于从小到大的加入过程保证了 \(y, p\) 都升序，所以这个 \(p_i\) 贡献的逆序对数即为 \([i + 1, n]\) 中已经被确定（包含在 \(S\) 中）的 \(j\) 的数量，设其为 \(t\)。那么我们有 \(f_{S, k} \gets f_{S \setminus \{i\}, k - 1} \times (-1)^t \binom{m}{k - x_i}\)。
时间复杂度 \(O(2^n (m + x_n))\)。
code
// Problem: H - Random Robots
// Contest: AtCoder - AtCoder Beginner Contest 216
// URL: https://atcoder.jp/contests/abc216/tasks/abc216_h
// 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 mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2100;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
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], f[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;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 0; i < n; ++i) {
scanf("%lld", &a[i]);
++a[i];
}
fac[0] = 1;
for (int i = 1; i <= m; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[m] = qpow(fac[m], mod - 2);
for (int i = m - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
f[0][0] = 1;
for (int S = 0; S < (1 << n); ++S) {
for (int x = 1; x <= 2005; ++x) {
f[S][x] = (f[S][x] + f[S][x - 1]) % mod;
int t = 0;
for (int i = n - 1; ~i; --i) {
if ((~S) & (1 << i)) {
continue;
}
f[S][x] = (f[S][x] + (t ? mod - 1 : 1) * f[S ^ (1 << i)][x - 1] % mod * C(m, x - a[i])) % mod;
t ^= 1;
}
}
}
printf("%lld\n", f[(1 << n) - 1][2005] * qpow(inv2, n * m) % mod);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}