2019-10-23测试总结
Eqvpkbz's Site

2019-10-23测试总结

考到自闭了,是真的令人无F**K说

$a$

题目大意

一个三维坐标图,有$m$个点不能走,从$(0,0,0)$$(n,n,n)$的路径方案数
给定$n,m,$不能走的点的坐标,求方案数对$(1e9 + 7)$的余数

数论题

不难推出无障碍时从$(0,0,0)$$(n,n,n)$的路径方案数为

$$\dbinom{2n}{n} * \dbinom{3n}{n} = \frac{(3n)!}{n!*n!*n!}$$

然后可以推广到:

无障碍时从$(0,0,0)$$(x,y,z)$的路径方案数为

$$\frac{(x + y + z)!}{x!*y!*z!}$$

再推广一下有障碍时的情况

$f_i$表示不经过障碍时的到达第$i$个障碍的路径条数,第i个障碍点的坐标为$(x_i,y_i,z_i)$

然后可以递推求解得:

$$f_i = \frac{(x_i + y_i + z_i)!}{x_i!*y_i!*z_i!} - \sum\limits_{x_j \leqslant x_i,y_j \leqslant y_i,z_j \leqslant z_i}{} f_j*\frac{(x_i - x_j +y_i - y_j +z_i - z_j)!}{(x_i - x_j)!*(y_i - y_j)!*(z_i - z_j)!}$$

然后就可以$O(m^2)$递推了

$b$

我不会

$c$

我还是不会