Combination

有趣题。 首先答案相当于要求三个矩阵里枚举三个点，然后求 AB 的路径数乘上 BC 之间的路径数加起来。 然后这个东西呢，我们先考虑假如 A 和 B 都固定的情况，我们发现是一个矩形。 然后我们根据一个叫曲棍球棒恒等式的东西我们很容易写出其为： $$ f(x_r + 1, y_r + 1) + f(x_l, y_l) - f(x_r + 1, y_l) - f(x_l, y_r + 1); $$ 然后我们就有平方做法了。 然后我们怎么继续优化？ 我们首先发现这个式子是可以拆的，拆成十六个问题，每个问题相当于给起点和终点要求午饭点。 然后我们还是想着差分对吧，然后我们就把他差分成：午饭区域是一个以起点为左下角的长方形。 然后我们惊奇的发现我们可以枚举我们从哪个边界出这个矩形的，因为我们知道了这个之后我们可以方便算出有多少种方案，更重要的是——在经过固定边界的一条路径上的午饭点的数量是相同的，我们直接乘起来就可以了。 然后就大概是超大常数 $O(n)$。