B번 문제인데 나름 까다로운 예외케이스가 존재한다.

n행, m열 이 주어질 때, n-1, m-1 개로 만들 수있는 모든 경우의수가 답이된다

이 때 짝수행, 홀수열 이나 홀수행, 짝수 열인 경우 -1 이 오게되면 답이 존재하지 않는다.


또한 범위가 10 의18승이므로 단순한 n*m 으로는  long long 조차 오버플로우가 난다.

따라서 리턴값에 함수를 한번더 사용하였다. 시간복잡도 O(log^2)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <algorithm>
 
#include <vector>
 
using namespace std;
typedef long long ll;
ll n,m,k;
const ll mod = 1000000007;
 
ll mypow(ll a,ll b,ll c){
    ll ret = 1ll;
    while(b>0){
        if(b&1){
            ret = (ret * a) % c;
        }
        b /= 2;
        a = (a*a) %c;
 
    }
 
return ret;
}
int main(){
    freopen("input.txt","r",stdin);
scanf("%lld %lld %lld",&n,&m,&k);
 
if( k== -1){
    if(n%2 && !(m%2)){
        puts("0");
        return 0;
    }
    if(!(n%2&& m%2){
        puts("0");
        return 0;
    }
 
}
 
printf("%lld",mypow(mypow(2ll,m-1,mod),n-1,mod )) ;
 
 
 
 
 
}
cs


'알고리즘' 카테고리의 다른 글

L-R flow : 하한이 있는 플로우  (0) 2018.03.31
유량 테크닉  (0) 2018.03.31
codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26
acm-cicpc 수학정복  (2) 2017.09.15
[BOJ1168] 조세퍼스 문제2  (0) 2017.01.22

+ Recent posts