简单的计数

发布时间: 2018年10月20日 00:46   最后更新: 2018年10月20日 00:59   时间限制: 3000ms   内存限制: 128M

众所周知,一张 $a*b$ 的网格图从左下角走到右上角的方案数(只允许向上或者向右走)是十分容易计算的,那么对于所有的这些方案,他所走过的网格面积是多少呢?

(例如下面 $4*3$ 的网格图上的这条可行路径,他所走过的网格面积即为 $6$ )

p638_lattice_area.png

这当然也是个 $trivial$ 的问题,但是我更想知道的是,如果我们把一张$a*b$的网格图的一种可行走法所走过的网格面积记为 $A(P_{a,b})$ ,给出一个常数 $k$ ,那么对这张网格图的所有的可行走法, $k^{A(P_{a,b} )}$ 的总和是多少呢?

第一行输入一个数字$T$表示测试数据组数。
接下来的 $T$ 行每行输入三个数字分别代表该组数据的 $a,b,k$ 。
$T \leq 20$
$1 < a,b < 10^6$
$1 < k < 10$

对于每组数据,输出答案对 $10^9+7$ 取模后的结果即可。

复制
2
2 2 2
15 10 3
35
880419838

对于第一组样例,$35 = 2^0+2^1+2^2+2^2+2^3+2^4$

math

Project Euler