好矩阵

[编程题]好矩阵

热度指数：550 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。

例如：

是好矩阵，两个2*2的子矩阵的和分别是8和12。

请问 $n$ 行 $m$ 列，矩阵中每个数均在 $[1,x]$ 范围内的好矩阵有多少种？由于答案过大，请对 $10^9+7$ 取模。

数据范围： $2\leq n,m,x \leq 10^9$
保证 $x$ 为偶数。

示例1

输入

2,2,2

输出

说明

合法的8个矩阵为：

算法知识视频讲解

Python

pein531

这题是个挺难的数学题，楼上大佬的分析已经写得很详细了，这里补一个python的写法，感受一波python的简洁

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param m int整型 
# @param x int整型 
# @return int整型
#
class Solution:
    def numsOfGoodMatrix(self, n: int, m: int, x: int) -> int:
        # write code here
        MOD = int(1e9 + 7)
        return pow(x >> 1, n*m, MOD)*pow(2, n + m - 1, MOD) % MOD

编辑于 2023-02-02 17:50:40 回复(1)