CF 894B Ralph And His Magic Field

题目描述

http://codeforces.com/problemset/problem/894/B

简要题意：给定一个 $n\times m$ 的矩形，要求在每个位置填 $0$ 或 $1$，要求每一行和每一列的异或和都是 $k$，求方案数

$1\le n,m\le 10^{18}$

Solution

注意到我们前 $n-1$ 行 $m-1$ 列无论怎么填，最后一行和最后一列都能选择对应的数字满足条件

需要注意的是如果 $|n-m|$ 是奇数且 $k=-1$ 的情况是无解的

其他情况下答案就是 $2^{(n-1)\times (m-1)}$

#include <iostream>
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

ll n, m, k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;
    if ((abs(n - m) & 1) && k == -1) return cout << 0 << "\n", 0;
    cout << pow_mod(pow_mod(2, n - 1), m - 1) << "\n"; 
    return 0; 
}