알고리즘/BOJ

[백준] 15710 xor 게임

세진짱 2018. 7. 9. 21:20


a라는 수를 n번 턴동안 xor 시켜서 b로 가면 된다

문제가 참 생각만 한다면 쉽게 풀 수 있다


생각해보면 모든수가 있기 때문에 a에서 b로 xor 한번만에 무조건 갈수있다

그럼 n번의 경우동안 한번 b로갈 경우 1번 미리 빼두자

n-1번 동안은 내맘대로 해도 된다


그리고 갈 수 있는 경우는 계속 2^31이 된다(모든 수로 가는게 가능)

결국 답은 2^31^(n-1)이 된다!


lgN만에 구해주자~!


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
ll a, b, n;
ll mod = 1e9 + 7;
ll mypow(ll x, ll y) {
    if (!y) return 1;
    if (y & 1return x*mypow(x, y - 1) % mod;
    return mypow((x*x) % mod, y / 2) % mod;
}
int main() {
    scanf(" %lld %lld %lld"&a, &b, &n);
    n--;
    ll w = mypow(231);
    ll ans = mypow(w, n);
    ans %= mod;
    printf("%lld\n", ans);
}
cs