我要招人

去企业版

首页 > 试题广场 >

好矩阵

[编程题]好矩阵

热度指数：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个矩阵为：

算法知识视频讲解

澪语

class Solution {
public:
    int mod = 1e9 + 7;
    int func(long long a, long long b) {
        long long res = 1;
        while (b)
        {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res % mod;
    }
    int numsOfGoodMatrix(int n, int m, int x) {
        long long a = n;
        a *= m;
        long long ans = func(x / 2, a);
        ans *= func(2, n + m - 1);
        ans %= mod;
        return ans;
    }
};

题目规定X为偶数，也就说奇数和偶数的数量均为a = x / 2。

对于第一列，每个位置可以有x种数字，所以第一列的所有可能的种类为A = x^n。

对于确定的一列，如果新增一列后是好矩阵，可以证明只有两种情况：

1.每一行的奇偶性与前一列完全相同；

2.每一行的奇偶性与前一行完全相反。

这两种情况的种类均为a^n（a = x / 2）。

因为有两种情况，所以新增一列，可能的种类数就要乘上B = 2 * (a^n)。

那么对于m列，答案就是乘上m - 1次2*（a^n）。

所以，最终结果为：A * B^(m - 1)。

化简得a^(nm)*2^(n + m - 1)。

由此引入了一个新的问题，即a的b次方对p取模怎么算，这个问题在牛客竞赛里有，感兴趣的可以在这里看一下：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=53784228

这个问题可以用模运算的性质来解决，大家可以看代码中的func函数，时间复杂度度为o(logn)。

计算原理这里就不证明了，如果有不懂的可以在评论区留言，看到后会进行解答。

编辑于 2022-09-29 19:14:37 回复(4)

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)

爱萝莉

曼陀罗佬的代码很清晰了，我只想说，n*m有可能会超int！！写的时候要小心。如果是long long a = n*m是不过的，要long long a=n;a*=m;才过，/(ㄒoㄒ)/~~

发表于 2022-10-18 11:30:07 回复(1)

darvec

做了半天发现X保证是偶数🤮

发表于 2023-08-22 04:07:50 回复(0)

Sakura丶薄荷

首先第一列随意，可以有x**n种选择；

第一列中相邻的两个元素可能是

第

一

列

奇

偶

奇

偶

第二列分两种情况，奇偶性和第一列对应的完全相同、完全不同，每一种皆是（x/2）**n中选择，转化为数学问题解答。

发表于 2023-08-11 16:12:24 回复(1)

朴小明

const mod int = 1e9 + 7

func qpow(x, n int) int {
	ans := 1
	for n > 0 {
		if n&1 == 1 {
			ans = ans * x % mod
		}
		x = x * x % mod
		n >>= 1
	}
	return ans
}
func numsOfGoodMatrix(n, m, x int) int {
	ans := qpow(x, m) * qpow(2, n - 1) % mod * qpow(x / 2, m * (n - 1)) % mod
	return ans
}

发表于 2023-03-23 19:53:03 回复(0)

开开开开开开心

冲啊

发表于 2023-03-09 20:10:09 回复(1)

牛客214419622号

#include <bits/stdc++.h> using namespace std; const int mod = 1e7; typedef long long LL; LL res = 0, n, m, x; LL f1[mod], f2[mod]; LL v1, v2; LL vs1[mod], vs2[mod]; LL C[mod]; int main() { cin >> n >> m >> x; v1 = (x % 2 == 0) ? x / 2 : x / 2 + 1; // 奇数  v2 = x / 2; C[0] = 1; for (int i=1;i<=m;i++) { for (int j=m;j>=1;j--) { C[j] = C[j] + C[j-1];
        }
    } vs1[0] = vs2[0] = 1; for (int i = 1; i <= m; i++) { vs1[i] = vs1[i - 1] * v1; vs1[i] %= mod; vs2[i] = vs2[i - 1] * v2; vs2[i] %= mod;
    } for (int i = 0; i <= m; i++) { f1[i] = vs1[i] * vs2[m - i]; f1[i] %= mod;
    } for (int i = 2; i <= n; i++) { for (int j = 0; j<= m; j++) { f2[j] = f1[j] + f1[m - j]; f2[j] %= mod; f2[j] *= C[j]; f2[j] %= mod;
        }
        memcpy(f1, f2, sizeof f2);
    } for (int i = 0; i <= n; i++) { res += f1[i]; res %= mod;
    } cout << res; return 0;
}