我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有22的子矩阵数字和为偶数。例如：是好矩阵，两个22的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。

区块链毕设网qklbishe.com为您提供问题的解答

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

例如：

我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。
是好矩阵，两个2*2的子矩阵的和分别是8和12。

请问 $我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。$ 行 $我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。$ 列，矩阵中每个数均在 $我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。$ 范围内的好矩阵有多少种？由于答案过大，请对 $我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。$ 取模。

数据范围： $我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。$
保证 $我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。例如：是好矩阵，两个2*2的子矩阵的和分别是8和12。请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。数据范围：保证为偶数。$ 为偶数。

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取模怎么算，这个问题在牛客竞赛里有，感兴趣的可以在这里看一下：

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

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

编辑于 2022-09-29 19:14:37

#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; }