问题 G: 我觉得OK

问题 G: 我觉得OK

时间限制: 3 Sec  内存限制: 512 MB
提交: 23  解决: 5
[状态] [讨论版] [提交] [命题人:]
题目描述
现在有一个巨大的矩形网格地图,小明最开始在左上角,他梦想的大学在右下角,小明想走到他梦想的大学,他每次只能向下或者向右走一步,并且其中有一部分点是不能走的…
“诶,这个题很显然是个数学题,直接一个Lucas板子套一套,然后容斥一波不就好了,我都已经猜到你的套路了。”
这…为什么你们什么题都写过,不行了,我要加条件。因为我们的小明比较zz,所以他走路也可以变得zz。于是我们的小明走路就变成了下面这个样子:
他不仅可以向下向右走,还可以每次按照上图的轨迹斜着走一步(只能从右上向左下)。那么根据小明的移动规律,我们可以计算出他到达任意一个点的方案数。
由于这个大矩形是非常非常大的,为了简化问题,现在已知到达大矩形内右下角的n*m的小矩形的第一行和第一列的每个点的路线的方案数,以及一些不能走的坏点,请计算出小明到达梦想的大学路线的总方案数。
(设小矩形左上角为(1,1))

输入
第一行三个整数,n(1<=n<=10),m(1<=m<=10),k(0<=k<=n*m)表示一个n行m列的小矩阵,其中有k个坏点。
接下来是n行,其中第一行有m个整数,第i个表示到达小矩形第一行第i个点(1,i)的方案数的值w,之后的n-1行,每行一个数字,第j个数字表示到达小矩形的第一列第j+1个点(j+1,1)的方案数的值w。(w<=1e18)
然后是k行,每行两个整数表示坏点在小矩形中的坐标,坏点不会出现在小矩形的第一行和第一列。
注:无需考虑给出的上边界、左边界的方案数的合法性

输出
一行,表示答案。

样例输入 Copy
3 3 1
1 1 1
1
1
2 2
样例输出 Copy
3