我们定义一个矩阵为“好矩阵”,当且仅当该矩阵所有2*2的子矩阵数字和为偶数。 例如: 是好矩阵,两个2*2的子矩阵的和分别是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; } 

13:51

承接区块链项目定制开发

微信:btc9767

QQ :1330797917

TELEGRAM: BTCOK9

承接区块链项目定制开发


qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台-javagopython毕设 » 我们定义一个矩阵为“好矩阵”,当且仅当该矩阵所有2*2的子矩阵数字和为偶数。 例如: 是好矩阵,两个2*2的子矩阵的和分别是8和12。 请问行列,矩阵中每个数均在范围内的好矩阵有多少种?由于答案过大,请对取模。 数据范围: 保证为偶数。

发表回复