526互联

AtCoder Beginner Contest 216 H Random Robots

发布时间 2023-10-27 10:40:32作者: zltzlt

洛谷传送门

AtCoder 传送门

下文令 \(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}\)。

也就是说我们现在需要知道所有 \(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;
}