1.dp 相关
1.1 path
给定一个 \(n∗m\) 的网格，你在左下角 \((n,1)\)，一开始你面向上方，你只能往前走或者右拐，障碍和走过的点不能走。
求走到 \((x,y)\) 的方案数的值，取模。 \(n,m\le 40\)
观察到一右拐，就会进入一个子矩形，并只能在这里面移动了。
设状态 \(f(a,b,x,y,0..3)\) 表示从矩形 \((a,b,x,y)\) 的左上角，右下角，左下角，右下角进入这个矩形，
往后一直在这个矩形内运动，到达终点的方案数。
转移是容易的，只需要枚举在当前方向上走了多少步，然后右拐转移即可。