Escape

构造 + 组合

题意：在n*m的网格表示的街道图内，移动时需要走格线，每个交点最多可以经过一次，在交点处可以选择直行或右转。问从起点(0,0)出发到终点(x,y)最多有多少种走法。

这题想了很久也没头绪，然后看了看discuss里有人提示用”转弯次数”+”组合数”分类讨论，然后细心推了一下：从起点到终点之间的路径，总是纵横交错的。并且其中纵向部分，南北两向总是交替出现的；横向部分同理。通过进一步分析可以发现，若确定了一条路径的转弯次数，那么其中横向和纵向的部分是相互独立的，也即该转弯次数对应的路径总数为横向部分的方案数与纵向部分方案数的乘积。横向、纵向的方案数是可以分别通过组合数来计算出来的。在某方向上，每次拐弯的位置必须是交错地位于终点坐标两侧的，那么总方案数即为从两侧选择拐弯位置的总可能数。例如，横向坐标范围0~4，终点在3时，那么横向拐2次弯的总方案数为C(1,1)*C(3,1)，即先从4~4里面选一个位置拐一次，再从0~2里面选一个位置拐一次。不存在拐3次或以上弯的可能性。

到这里为止的推算还算是顺利的，倒是在计算C(n,k)上卡了很久的TLE。考虑了很久如何在模系统中实现除法，未果。于是开始分解质因数再累加，并想了各种优化……但都TLE了。最后才想起来可以利用C(n,k)=C(n-1,k)+C(n-1,k-1)来预处理出整个int C[2002][2002]，于是就AC了。