BOJ 28089 - 응애(HARD)

문제

처음에는 "이게 풀린다고?" 싶었는데, 몇 번 관찰을 거듭하니 나름 무난했던 문제다.

 

문제 요약:

$N$명의 사람이 원형으로 앉아 있다. 한 사람이 인사를 하면, 그 양 옆에 있는 두 사람은 1초 뒤에 인사를 해야 한다. 단, 자신의 양 옆에 있는 두 사람이 동시에 인사했다면, 인사하지 않는다. 0초에 인사하는 사람의 목록이 주어질 때, $K$초 뒤 인사하는 사람의 수를 구하라.

 

$3 \leq N \leq 2\,000\,000; 0 \leq K \leq 10^{18}$

 

풀이:

1. 인사하는 상태를 1, 인사하지 않는 상태를 0으로 나타냈을 때, 어떤 사람의 1초 뒤 상태는 그 사람의 양옆 상태를 XOR한 값이다.

 

사실 당연한 말인데, 이걸 숨기려고 지문이 교묘하게 작성되어 있는 것 같다. 

 

2. $x$초가 지났을 때 $i$번 사람의 상태를 $A_x(i)$라고 하자.

 

$A_1(i) = A_0(i-1)$^$A_0(i+1)$이다. (편의상 인덱스의 모듈러는 생략한다.) 

$A_2(i) = A_1(i-1)$^$A_1(i+1) = A_0(i-2)$^$A_0(i+2)$이다.

$A_4(i) = A_2(i-2)$^$A_2(i+2) = A_0(i-4)$^$A_0(i+4)$이다.

 

같은 방식으로, 모든 2의 거듭제곱 $x$에 대해,

$A_x(i) = A_0(i-x)$^$A_0(i+x)$

임을 알 수 있다.

 

3. 따라서, $k$의 켜져있는 비트마다 모든 사람의 상태를 업데이트해주면 된다. 

 

시간 제한이 상당히 빡빡해서, 비트셋 사용 + 반복문 안에서 모듈러를 사용하지 않는 최적화를 한 후에야 맞았습니다를 받았다.

 

빠른 거듭제곱을 쓰긴 했는데, 사실 생각해 보니 거듭제곱 결과가 최대 $2^{60}$밖에 안 돼서 빠른 거듭제곱은 쓸 필요가 없다. 

 

코드:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bitset<2'000'200> v;
ll N, M, K;
ll pw(ll n, ll ex)
{
    if (ex == 0)
        return 1;
    ll tmp = pw(n, ex / 2);
    if (ex % 2 == 0)
        return tmp * tmp % N;
    return tmp * tmp % N * n % N;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++)
    {
        ll a;
        cin >> a;
        v[a] = 1;
    }
    for (int i = 60; i >= 0; i--)
    {
        if (K & (1LL << i))
        {
            K -= (1LL << i);
            bitset<2'000'200> t;
            int g = pw(2, i);
            int l = ((-g) % N + N) % N, r = g % N;

            for (int j = 0; j < N; j++)
            {
                t[j] = v[l] ^ v[r];
                l++, r++;
                if (l >= N)
                    l -= N;
                if (r >= N)
                    r -= N;
            }
            v = t;
        }
    }
    cout << v.count();
}