我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。 例如： 是好矩阵，两个2*2的子矩阵的和分别是8和12。 请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。 数据范围： 保证为偶数。
区块链毕设网qklbishe.com为您提供问题的解答
我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有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; }
13:51
以上就是关于问题我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。 例如：
是好矩阵，两个2*2的子矩阵的和分别是8和12。
请问行列，矩阵中每个数均在范围内的好矩阵有多少种？由于答案过大，请对取模。
数据范围：
保证为偶数。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
