题解 | #好矩阵#

链接

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)。 计算原理这里就不证明了，如果有不懂的可以在评论区留言，看到后会进行解答。