5216. 다항식의 계수

이 주어졌을 때 의 계수%3을 구하는 문제다.

n의 범위가 1e15고 tc가 36000개라 O(n)으로는 안풀린다. trinomial coefficient 문제다.

입력만 봤을때는 분할정복 혹은 이분탐색 문제로 추정된다.

접근 1. 

패턴을 찾자. %3은 괜히 한게 아닐것이다.

실제 값으로 배열을 만들어 출력하다 보니 다음과 같은 패턴이 나왔다. 0은 흰색, 1은 초록색, 2는 빨간색으로 표시했다.

잘 살펴보면 가장 큰 삼각형은 3단으로 나뉘어 지고 또 나뉘어 지는 것을 반복하는 것을 알 수 있다. 또한 삼각형을 차례대로

  1

 234

56789  

모양으로 보자.

1. 1,5,7,9는 삼각형 자기자신의 형태에서 크기만 1/3로 줄어든 형태임을 알 수 있다.

2. 원래의 삼각형(아랫변이 111111인)은 꼭지점이 1,111 이런식으로 시작하지만 2,4는 12,1002 이런식으로 변한 것을 알 수 있다. 또한 2,4 내부의 2,4번째 삼각형은 다시 1,111 순으로 시작하는 것도 보인다.

3. 2,4번은 각 삼각형의 중심을 기준으로 데칼코마니 형태를 가진다.

4. 1,111로 시작하는 서브삼각형의 3단 높이는 차례대로 14,13,14고 12,1002로 시작하는 서브삼각형의 3단 높이는 13,14,13으로 총합에서 1차이가 난다. 1,111로 시작하는 삼각형을 a, 다른것을 b로 표현하면

a는

  a

 b b'

a a a

b는

  b

 a a'

b b b

형태를 가진다.

5. n == 1+3+9+...3^m 위치에는 무조건 1111...11111 모양이 존재한다.

접근 2.

위에서 구한 규칙성을 이용한다. 

1. 현재 있는 삼각형의 꼭지점 형태를 type이라는 변수에 저장한다.

2. 2,4번 삼각형의 경우를 위해 left_flipped, right_flipped라는 변수를 사용한다.

2번에 걸리면 right_flipped = 1 - right_flipped

4번에 걸리면 left_flipped = 1 - left_flipped

이런식으로 저장한다. 삼각형의 형태와 뒤집어진 것은 내부의 삼각형에서 계속 유지가 되므로 저런식으로 저장해야 한다.

계산순서

1) n,k를 가지고  위치를 찾는다.

2) 저 두 값의 평균값이 234 / 56789 번 삼각형을 나누는 위치이므로 그 값을 기준으로 현재 어느 위치인지 계산해 들어간다.

3) 쭉 타고 들어가다가 내가 정한 최소단위의 삼각형이 된다면 거기서 위치를 찾아 출력하자.

4) 시간복잡도는 이 된다.

※ type에 따라서 움직여야 하는 양이 조금씩 차이나는데 실수하면 화가난다. 조심하자.

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
ll t, n, k;
ll p[34];
// type, left, right
ll arr[2][2][2][5][12]{
    {
        {
            {    //0,0,0
                { 1 },
                { 1,1,1 },
                { 1,2,0,2,1 },
                { 1,0,0,1,0,0,1 },
                { 1,1,1,1,1,1,1,1,1 }
            },
            {    //0,0,1
            }
        },
        {
            {    //0,1,0
 
            },
            {    //0,1,1
                { 2 },
                { 2,2,2 },
                { 2,1,0,1,2 },
                { 2,0,0,2,0,0,2 },
                { 2,2,2,2,2,2,2,2,2 }
            }
        }
    },
    {
        {
            {    //1,0,0
                { 1,1 },
                { 1,0,0,1 },
                { 1,1,1,1,1,1 },
                { 1,2,0,1,1,0,2,1 }
            },
            {    //1,0,1
                { 1,2 },
                { 1,0,0,2 },
                { 1,1,1,2,2,2 },
                { 1,2,0,1,2,0,1,2 }
            }
        },
        {
            {    //1,1,0
                { 2,1 },
                { 2,0,0,1 },
                { 2,2,2,1,1,1 },
                { 2,1,0,2,1,0,2,1 }
            },
            {    //1,1,1
                { 2,2 },
                { 2,0,0,2 },
                { 2,2,2,2,2,2 },
                { 2,1,0,2,2,0,1,2 }
            }
        }
    }
};
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    p[1] = 1;
    for (int i = 2; i < 34; ++i) p[i] = p[i - 1] * 3LL;
    for (int i = 2; i < 34; ++i) p[i] += p[i - 1];
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        cin >> n >> k;
 
        ll ts = upper_bound(p, p + 34, n) - p;
        ll type = 0;
        ll left_flipped = 0;
        ll right_flipped = 0;
        ll ans = -1;
 
        while (ts > 2 && ans == -1) {
            ll mid = (p[ts - 1] + p[ts]) / 2;
 
            if (n == p[ts - 1] && !type) {
                ans = 1 + (left_flipped + right_flipped) / 2;
            }
            else if (n == p[ts - 1] - 1 && type) {
                ans = (k + 1) % 3;
                if (k <= n) {
                    if (left_flipped) {
                        if (ans == 2) ans = 1;
                        else if (ans == 1) ans = 2;
                    }
                }
                else {
                    if (right_flipped) {
                        if (ans == 2) ans = 1;
                        else if (ans == 1) ans = 2;
                    }
                }
            }
            else if (k == 0) {
                ans = 1 + left_flipped;
            }
            else if (k == 2 * n + 1) {
                ans = 1 + right_flipped;
            }
            // 56789
            else if (n > mid) {
                while (k - mid > 0) k -= mid + 1;
                if (k < (n - mid) * 2 - 1 + type) {
                    n -= mid + 1;
                }
                else {
                    ans = 0;
                }
            }
            // 234
            else {
                // left
                if (k < (n - p[ts - 1]) * 2 + type) {
                    right_flipped = 1 - right_flipped;
                }
                // right
                else if (k > mid) {
                    k -= mid + 1;
                    left_flipped = 1 - left_flipped;
                }
                else {
                    ans = 0;
                }
                type = 1 - type;
                n -= p[ts - 1] + type;
            }
            ts = upper_bound(p, p + 34, n) - p;
        }
 
        cout << "#" << tc << " " << (ans == -1 ? arr[type][left_flipped][right_flipped][n][k] : ans) << '\n';
    }
    return 0;
}