6719：Strassen

题目描述

在本题中，我们只有两种方法计算两个$n\times n$的矩阵的乘积，第一种为定义法，需要$n^3$次乘法和$(n-1)n^2$次加法。第二种为Strassen分治法，仅当$n$为偶数时可以使用，需要$18(n/2)^2$次加法以及再计算$7$次大小为$(n/2)\times(n/2)$的矩阵的乘积。这$7$次更小矩阵的乘积也可以选择两种方法之一计算。现假设计算机计算一次加法需要$a$单位时间，计算一次乘法需要$b$单位时间，其他任何操作不花费时间，问计算两个$n\times n$的矩阵的乘积至少需要多少时间。输出答案模$10^9+7$的余数。

输入解释

第一行一个正整数$t$表示数据组数（$1\le t \le 20$）。
每组数据包含一行三个正整数$n$，$a$，$b$（$1\le n\le 2^{32}$，$n$是$2$的幂，$1\le a\le 10^9$，$1\le b\le 10^9$）。

输出解释

每组数据输出一行，包含一个整数表示答案模$10^9+7$的余数。

输入样例

1
16 1 1

输出样例

来自杭电HDUOJ的附加信息

Recommend

liuyiding

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2019 年百度之星·程序设计大赛 - 初赛四

源链接： HDU-6719

最后修改于 2020-10-25T23:33:47+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	32768/32768K(Java/Others)