题解：AT_abc216_h [ABC216H] Random Robots

· · 题解

Solution

把机器人转化为从平面上 (n,x_i) 往 (0,*) 走，从 (i,j) 能到 (i-1,j) 或者 (i-1,j+1) 走，进行不相交格路计数。

考虑用 LGV 引理。保证终点递增的情况下，\det(M_{i,j} = cnt((0,y_i),(n,t_j))) 算行列式就是不相交格路数。

但是终点是不确定的，所以考虑对终点集合做 DP。考虑在矩阵的后若干行每行选出一列，构成了集合 S。这样将一个元素加入 S，它在行列式中产生的共线（逆序对个数的奇偶性）是已知的，直接 DP 即可。

复杂度 O(k2^k V)。

AC Link