Codeforces Round #447(Div.2) B. Ralph And His Magic Field(수론, 조합 수학)

Description
Ralph has a magic field which is divided into n × m blocks. That is to say, there are n rows and m columns on the field. Ralph can put an integer in each block. However, the magic field doesn’t always work properly. It works only if the product of integers in each row and each column equals to k, where k is either 1 or -1.
Now Ralph wants you to figure out the number of ways to put numbers in each block in such a way that the magic field works properly. Two ways are considered different if and only if there exists at least one block where the numbers in the first way and in the second way are different. You are asked to output the answer modulo 1000000007 = 109 + 7.
Note that there is no range of the numbers to put in the blocks, but we can prove that the answer is not infinity.
Input
The only line contains three integers n, m and k (1 ≤ n, m ≤ 1018, k is either 1 or -1).
Output
Print a single number denoting the answer modulo 1000000007.
Examples
input

1 1 -1

output

1

input

1 3 1

output

1

input

3 3 -1

output

16

Note
In the first example the only way is to put -1 into the only block.
In the second example the only way is to put 1 into every block.
사고의 방향
n∗m의 네모난 칸이 있는데 그 안에 숫자를 기입해야 한다. 각 줄과 열의 곱셈이 모두 k이고 k의 값은 1 또는 -1이다. 모두 몇 가지 기입하는 방법이 있냐고 물었더니 결과는 매우 크다.
우리는 n∗m의 네모난 칸에 숫자를 채워서 마지막 줄과 열의 곱셈이 모두 1 또는 -1이 되도록 해야 한다. 그러면 각 작은 네모난 칸에 기입한 숫자는 1 또는 -1일 수 있다. 우리는 모든 줄을 고려한다. 앞(m-1)에 어떤 숫자를 기입하든지 간에 우리는 이 줄의 마지막 칸에 1 또는 -1을 기입해서 곱셈을 제목이 요구하는 것으로 만들 수 있다.그래서 문제는 (n-3-1)∗(m-3-1) 안에 있는 칸을 채우는 문제로 바뀌었다. 칸마다 1 또는 -1밖에 안 되기 때문에 답은 다음과 같다.
ans=2(n−1)∗(m−1)
그러나 우리는 k의 값이 -1일 때 (n+m)의 값이 홀수라면 아무리 채워도 제목의 요구를 충족시키지 못하고 마지막에 곱하면 반드시 1이 나타날 수 있으므로 k가 -1이고 (n+m)의 값이 홀수라면 0을 출력해야 한다는 것을 주의해야 한다.
또한 n과 m의 값은 모두 1e18까지 갈 수 있기 때문에 숫자가 비교적 크기 때문에 우리는 빠른 멱을 잡을 때 기교를 사용할 수 있다.
ans=(2n−1)m−1
이렇게 하면 데이터가 폭발하지 않도록 보장할 수 있다. 물론 이것은 c++에 대한 말이다. 어떻게 우리의 대py를 얻기 어려울 수 있겠는가!
코드 1(c++)

#include 
using namespace std;
typedef long long ll;
const ll N=1000+20;
const ll mod=1e9+7;
ll pow_mod(ll a,ll b,ll c)
{
    a%=c;
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    if(k==-1&&(n+m)&1) 
        puts("0");
    else
        printf("%lld
",pow_mod(pow_mod(2,n-1,mod),m-1,mod));
    return 0;
}

코드 2 (python3)

mod=int(1e9+7)
n,m,k=map(int,input().split())
if(k==-1 and (n+m)&1):
    print('0')
else:
    print(pow(2,(n-1)*(m-1),mod))