[백준] 15710 xor 게임

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

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

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

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

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

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

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

lgN만에 구해주자~!

소스코드

#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 & 1) return 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(2, 31);
    ll ans = mypow(w, n);
    ans %= mod;
    printf("%lld\n", ans);
}