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;
}
};
链接:https://www.nowcoder.com/questionTerminal/1359ea6a7cc24575af06727e3bd68f21?f=discussion 来源:牛客网
题目规定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)。 计算原理这里就不证明了,如果有不懂的可以在评论区留言,看到后会进行解答。