[ABC216H] Random Robots
题意
有 \(k\) 个机器人在数轴上, 位置分别是 \(x_1,x_2,\dots,x_k\) , \(x\) 均为整数.
接下来 \(n\) 秒, 每秒每个机器人有 \(\dfrac{1}{2}\) 的概率不动, \(\dfrac{1}{2}\) 的概率往坐标轴正方向移动一个单位距离, 机器人的移动同时进行.
求机器人互相不碰撞的概率, 对 \(998244353\) 取模。
\(k \le 10,n,x \le 1000\)。
思路
相当于求不碰撞的方案数，最后除以 \(2^{nk}\)。
设终点位置是 \(y_i\)。
加一维时间维，即 \((x,y)\) 可以走到 \((x+1,y)\)（不走）或者 \((x+1,y+1)\)（向右走一步），不碰撞即路径没有公共点。
容易想到 LGV 引理。但是不能乱套哦。
假设我们已经确定了 \(\{y_i\}\)。且这是一个升序序列。这是一个分层图。
算每个 \(0,x_i\) 都走到 \(y_i\) 的方案数是好算的，就是 \(\prod_{i=1}^n \binom{n}{y_i-x_i}\)。
那么他们在中间相交怎么办呢？
经典容斥，要求两条路径不交的方案数，就用 \(至少交0次的方案数 - 至少交1次的方案数\)。求至少交一次的方案数，就是交换两条路径的终点，然后求无限制的方案数。
多条路径怎么做呢？就用 \(至少0对路径有交点 - 至少1对路径有交点 + 至少2对路径有交点 \cdots\)。
即对一个升序序列 \(\{y_i\}\)，答案就是 \(\sum_{p} (-1)^{sgn(p)} \prod_{i=1}^n \omega((0,x_i),(n,y_{p_i}))\)。
其中 \(sgn(p)\) 表示排列 \(p\) 的逆序对数。\(\omega((0,x),(n,y))=\binom{n}{y-x}\)。
根据 LGV 引理，可以求个行列式来计算。然而显然我们不能枚举 \(\{y_i\}\)。
注意到数据范围，考虑状压 DP。
设 \(f_{i,s}\) 表示处理到坐标 \(i\)，目前已经有状态为 \(s\) 的起点已经确定了终点，的合法方案数。状态数是 \(O(2^k x)\) 的。
转移就是枚举是否有一个起点选择位置 \(i\) 作为终点（显然合法方案不会有两个起点走到一个位置作为终点）。
枚举哪个起点选择 \(i\) 作为终点，新贡献的逆序对数是好算的，对连乘的贡献也是好算的。即：
\[f_{i,s} \gets f_{i-1,s}(不选)\\ f_{i,s\cup j} \gets (-1)^{cnt} \binom{n}{i-x_j} f_{i-1,s} (选j) \]其中 \(cnt\) 指新增逆序对个数，即 \(s\) 的低 \(j-1\) 位里面有多少个 \(0\)。
答案就是 \(f_{x,2^k-1}\)。
时间复杂度 \(O(2^k x k)\)。
code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace pragmatic {
constexpr int N=15,V=2e3+1,mod=998244353;
int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
void _add(int &a,int b) { a=add(a,b); }
int mul(int a,int b) { return 1ll*a*b%mod; }
void _mul(int &a,int b) { a=mul(a,b); }
int ksm(int a,int b=mod-2) {
int s=1;
while(b) {
if(b&1) _mul(s,a);
_mul(a,a);
b>>=1;
}
return s;
}
int jc[V+7],inv[V+7];
void init() {
jc[0]=1;
rep(i,1,V) jc[i]=mul(jc[i-1],i);
inv[V]=ksm(jc[V]);
per(i,V-1,0) inv[i]=mul(inv[i+1],i+1);
}
int binom(int n,int m) {
if(n<m || m<0) return 0;
return mul(jc[n],mul(inv[m],inv[n-m]));
}
int k,n,x[N];
int f[V+7][V+7];
void main() {
sf("%d%d",&k,&n);
rep(i,1,k) sf("%d",&x[i]), ++x[i];
init();
f[0][0]=1;
rep(i,1,V) {
rep(j,0,(1<<k)-1) {
if(!f[i-1][j]) continue;
_add(f[i][j],f[i-1][j]);
int cnt=0;
rep(p,1,k) {
if(!((j>>(p-1))&1)) {
int tmp=mul(f[i-1][j],binom(n,i-x[p]));
if(tmp) _add(f[i][j^(1<<(p-1))],cnt ? mod-tmp : tmp);
cnt^=1;
}
}
}
}
pf("%d\n",mul(f[V][(1<<k)-1],ksm(ksm(2,n*k))));
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
pragmatic :: main();
}