"诶,这个题很显然是个数学题,直接一个Lucas板子套一套,然后容斥一波不就好了,我都已经猜到你的套路了."
这...为什么你们什么题都写过,不行了,我要加条件.因为我们的小明比较zz,所以他走路也可以变得zz.于是我们的小明走路就变成了下面这个样子:
他不仅可以向下向右走,还可以每次按照上图的轨迹斜着走一步(只能从右上向左下).那么根据小明的移动规律,我们可以计算出他到达任意一个点的方案数.
由于这个大矩形是非常非常大的,为了简化问题,现在已知到达大矩形内右下角的n*m的小矩形的第一行和第一列的每个点的路线的方案数,以及一些不能走的坏点,请计算出小明到达梦想的大学路线的总方案数.
第一行三个整数n(1<=n<=10)m(1<=m<=10)k(0<=k<=n*m)表示一个n行m列的小矩阵其中有k个坏点.
接下来是n行,其中第一行有m个整数,第i个表示到达小矩形第一行第i个点(1i)的方案数的值w,之后的n-1行,每行一个数字,第j个数字表示到达小矩形的第一列第j+1个点(j+11)的方案数的值w.(w<=1e18)
然后是k行,每行两个整数表示坏点在小矩形中的坐标,坏点不会出现在小矩形的第一行和第一列.