[ABC216H] Random Robots
题意：
有 \(k\) 个机器人在数轴上, 位置分别是 \(x_1,x_2,\dots,x_K\) , \(x\) 均为整数.
接下来 \(n\) 秒, 每秒每个机器人有 \(\dfrac{1}{2}\) 的概率不动, \(\dfrac{1}{2}\) 的概率往坐标轴正方向移动一个单位距离, 机器人的移动同时进行.
求机器人互相不碰撞的概率, 对 \(998244353\) 取模.
\(k \le 10,n \le 1000,x_{i} \le 1000\)。
分析：
统计方案数除以 \(2^{kn}\) 即为概率。
要求互相不碰撞，可以使用 LGV 引理，但终点没有确定，因此需要枚举最后 \(k\) 个机器人的位置 \(y_{1}<y_{2}<\dots<y_{k}\)，记 \(X_{i,j}=\binom{n}{y_{j}-x_{i}}\)。那么答案便是 \(\sum_{y} det(X)\)。考虑用行列式的定义去计算，先枚举 \(P\)（一个排列），那么它的贡献便是
\[(-1)^{τ(P)} \sum_{y} \prod_{j=1}^k\binom{n}{y_{p_{j}}-x_{j}}
\]
仍然不好计算，由于矩阵的转置的行列式不变，因此贡献也等于
\[(-1)^{τ(P)} \sum_{y} \prod_{j=1}^k\binom{n}{y_{j}-x_{p_{j}}}
\]
此时可以 dp，记 \(f_{i,j}\) 表示确定了 \(y_{1},y_{2},\dots,y_{i}\) 且 \(y_{i}=j\)，使用前缀和优化，总时间复杂度为 \(O(k!nk)\)。无法通过。
用一个二进制数 \(S\) 记录确定 \(P\) 的过程，具体地，记一个 \(f_{S,j}\) 表示当前排列 \(P\) 用过的数为 \(S\)，\(y_{i}=j\) 的方案数。需要枚举 \(P_{i}\) 的值，同样也要用前缀和优化，别忘了算上逆序对奇偶性的贡献。时间复杂度 \(O(2^{k}nk)\)。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 2010
#define mod 998244353
using namespace std;
int k, n, ans; //k:机器人的个数 n:时间
int x[N], sum[(1 << 10) + 5][12];
int f[(1 << 10) + 5][2010], g[(1 << 10) + 5][2010];
int cc[N][N];
int C(int n, int m) {
if(n < 0 || m < 0 || n - m < 0) return 0;
return cc[n][m];
}
int Pow(int a, int n) {
if(n == 0) return 1;
if(n == 1) return a;
int x = Pow(a, n / 2);
if(n % 2 == 0) return x * x % mod;
else return x * x % mod * a % mod;
}
int inv(int x) {
return Pow(x, mod - 2);
}
void upd(int &x, int y) {
x = (x + y + mod) % mod;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(int i = 0; i <= 2000; i++) cc[i][0] = 1;
for(int i = 1; i <= 2000; i++)
for(int j = 1; j <= i; j++) cc[i][j] = (cc[i - 1][j] + cc[i - 1][j - 1]) % mod;
cin >> k >> n;
for(int i = 1; i <= k; i++) cin >> x[i];
for(int S = 0; S < (1 << k); S++)
for(int i = k; i >= 1; i--) {
sum[S][i] = sum[S][i + 1];
if(S & (1 << (i - 1))) sum[S][i]++;
}
for(int S = 1; S < (1 << k); S++) { //p[1],p[2],...,p[i] : S[p[1]]=...=S[p[i]]=1
int i = 0;
for(int j = 0; j < k; j++)
if(S & (1 << j)) i++;
for(int j = 0; j <= 2000; j++) { //y[i]=j
for(int num = 1; num <= k; num++) { //p[i]=num
if(!(S & (1 << (num - 1)))) continue;
if(i == 1) {
f[S][j] = C(n, j - x[num]);
continue;
}
int lstS = (S ^ (1 << (num - 1))), z = 1;//z表示当前逆序对的奇偶性
if(sum[S][num + 1] % 2 == 1) z = -1;
if(j) upd(f[S][j], z * g[lstS][j - 1] * C(n, j - x[num]) % mod);
}
g[S][j] = (g[S][j - 1] + f[S][j]) % mod;
}
}
for(int i = 0; i <= 2000; i++) upd(ans, f[(1 << k) - 1][i]);
cout << ans * inv(Pow(2, k * n)) % mod;
return 0;
}