rutas-modificadas-contando-en-un-rectángulo

Restrinjamos el estudio solo a uno de los K rectángulos. Supongamos que N y M son respectivamente su alto y ancho, y que P y Q son el alto y el ancho del rectángulo que se corta. Vamos a referirnos a un sistema de coordenadas con origen en la esquina superior izquierda del rectángulo y los ejes x e y orientados hacia la derecha y hacia abajo respectivamente.

El número de caminos posibles desde la esquina superior izquierda hasta la esquina inferior derecha viene dado por:

$$\frac{(N+M)!}{N!M!}$$

Del número anterior debemos restar el número de caminos que no pasan por el rectángulo eliminado. Estos son todos los caminos que no tienen un punto en el segmento vertical (M-Q+1, 0) - (M-Q+1, P-1).

El número de caminos que pasan por un punto específico (x, y) viene dado por:

$$\frac{(x+y)!}{x!y!}\frac{[(M+N)-(x+y)]!}{(M-x)!(N-y)!}$$

Por lo tanto, el número que buscamos es:

$$\frac{(N+M)!}{N!M!}-\sum_{y=0}^{P-1}{\frac{(M-Q+1+y)!}{(M-Q+1)!y!}\frac{(N+Q-1-y)!}{(Q-1)!(N-y)!}}$$

Sin embargo, no sabría cómo poner esa suma en forma cerrada.

(Voy a desechar tu$x$subíndice, y considere un solo caso dado por$(N,M,P,Q)$. yo suelo$x$como mi$x$-coordinar.)

Dejar$H$Sea el segmento de línea horizontal de$(0,M-Q)$a$(N-P,M-Q)$que extiende el límite inferior del rectángulo recortado a lo largo de la parte sin cortar. Considere un punto$(x,y)$en$H$. Dejar$U(x,y)$sea ​​el número de caminos desde la esquina superior izquierda$(0,M)$a$(x,y)$ese primer encuentro$H$en$(x,y)$; y deja$L(x,y)$Sea el número de caminos desde$(x,y)$a la esquina inferior derecha$(N,0)$. Entonces el número de caminos desde$(0,M)$a$(N,0)$ese primer encuentro$H$en$(x,y$) es solo$U(x,y)L(x,y)$, y obtenemos el total al sumar esto$x$de$0$a$N-P$.

Ahora deja$R(i,j)$Sea el número de caminos desde una esquina de un$i \times j$rectángulo a la esquina opuesta:

$$R(i,j)=\frac{(i+j)!}{i!j!}$$ (como tú sabes). Recibimos de inmediato $L(x,y)=R(N-x,M-Q)$. Y para $U(x,y)$, tenga en cuenta que un camino que primero se encuentra $H$en $(x,y)$debe pasar $(x,y+1)$, entonces $U(x,y)$es solo $R(x,Q-1)$.

Partimos de la cuadrícula de esquina común (B, NA) del rectángulo y la parte cortada. Ahora, comenzamos desde la cuadrícula (0,0) y encontramos el camino hasta esa esquina multiplicado por los caminos desde esa esquina hasta la cuadrícula (N+1,M+1), es decir, el primer término de la expresión anterior. Ahora, retrocedemos una cuadrícula y calculamos la ruta desde la cuadrícula (0,0) hasta esa cuadrícula multiplicada por las rutas desde allí hasta la cuadrícula (N+1,M+1), pero eliminando los casos en los que se usa la cuadrícula común. De manera similar, siguiendo el proceso anterior hasta la cuadrícula (B,NA-1) a (B,0) obtenemos el resultado.

Por lo tanto, puede usar la fórmula que he derivado:

$${N-A+B \choose B} {M-B+A \choose A} + \sum_{r=0}^{N-A-1} {B+r \choose r} {N-r+M-B-1 \choose N-r}$$

dónde$A=P$y$B=Q$.

Necesita simplificarlo aún más para convertirlo en$O(n \log n)$solución.