[Python] 3462번 이진 스털링 수

 

https://www.acmicpc.net/problem/3462

3462번: 이진 스털링 수

---

 

23/11/29

 

 

학교 알고리즘 수업을 대비하기 위한 그룹에서 조합론 문제로 추천받아서 풀게 된 문제다.

 

규칙을 찾아서 풀기는 쉬운 난이도에 속하지만 증명이 좀 까다로운 편이라고 생각되어서 기존 난이도보다 한단계 높여서 난이도 기여를 했다.

---

 

문제 접근 방식:

 

 

문제에서 주어진 점화식을 활용하여 DP배열을 만들어 먼저 규칙을 찾아보기로 했다.

 

$N, M = 40$까지의 범위를 출력한 값은 다음과 같다.

 

출력한 모습

 

좀 멀리서 봐보자.

 

시에르핀스키의 삼각형 모양이 얼핏 보인다.

 

재귀적인 패턴이 보임을 한 눈에 확인할 수 있다.

 

세로 줄을 확인해보면, 다음과 같은 숫자가 반복됨을 확인할 수 있었다.

 

$$m = 1, 2 \rightarrow 1$$
$$m = 3, 4 \rightarrow 10$$
$$m = 5, 6 \rightarrow 1100$$
$$m = 7, 8 \rightarrow 1000$$
$$m = 9, 10 \rightarrow 11110000$$
$$m = 11, 12 \rightarrow 10100000$$
$$m = 13, 14 \rightarrow 11000000$$
$$m = 15, 16 \rightarrow 10000000$$
$$m = 17, 18 \rightarrow 1111111100000000$$
$$m = 19, 20 \rightarrow 1010101000000000$$
$$m = 21, 22 \rightarrow 1100110000000000$$
$$\cdots$$

 

이는 재귀적인 패턴임을 확인할 수 있다.

 

처음엔 $1$로 시작했고, 그 다음에는 $0$을 붙이고, 그 이후 2개는 이전 문자열들 모두 반복을 해서 같은 길이으로 만든 후에 $0$을 그 길이 만큼 더 붙이는 규칙임을 확인할 수 있었다.

 

 따라서 이를 구현하기 위해 먼저 $m$값을 통해 반복되는 패턴이 어떤 길이를 가지고 있는지 확인했다.

 

이후 현재 패턴 안에 어느 위치에 속하는지를 그 길이의 mod값을 통해 확인했다.

 

만약 그 길이의 절반보다 같거나 더 큰 위치에 있다면 $0$이라는 것은 확정이다.

 

그렇지 않는다면 우리는 뒤에 있는 절반의 $0$들을 모두 날려보내고 생각할 수 있다.

 

따라서 $m$값을 $m - \textrm{length}$의 값으로 바꿔서 똑같은 일을 반복하면 현재 위치가 $0$인지 $1$인지를 판단할 수 있게 된다.

 

나의 경우는 이렇게 패턴을 찾아서 구현 했는데, 다른 사람의 풀이를 찾아보니 다음과 같이 증명한 것이 있어서 가져왔다.

 

+) 덧붙여서, 시에르핀스키의 삼각형 모양은 !(i & j)를 사용하면 구현할 수 있다고 한다.

위의 모양에서 전치를 취해주고, 0부분을 제거한 뒤 같은 패턴이 반복되는 가로줄을 지우면 시에르핀스키의 삼각형 모양이 나옴을 확인할 수 있다. 이를 이용해 빠르게 구현할 수 있다.

---

 

원본 링크는 아래와 같다.

 

https://blog.naver.com/knoj014/222379888141

[BOJ 3462] 이진 스털링 수 풀이

 

여기서는 DP가 DAG라는 사실을 사용하여 간단하게 판단했다.

 

제2종 스털링 수의 mod2값은 기존 점화식에 의하면 다음과 같이 점화식을 쓸 수 있다.

 

$$S(n, m) = S(n-1, m-1) \textrm{ when m is even}$$

$$S(n, m) = (S(n-1, m-1) + S(n-1,m)) \textrm{ mod } 2 \textrm{ when m is odd}$$

 

이를 사용하여 적절하게 스털링 수를 바꾸면 다음과 같다.

 

$$\sum_{i=1}^na_iS(i, 0) + \sum_{i=1}^{m}b_iS(0, i) + cS(0, 0)$$

 

여기서 $a_i, b_i, c$는 모두 임의의 자연수이다.

 

즉, 다시 이야기 하자면, 임의의 스털링 수는 항상 $S(i, 0)$과 $S(0, j)$와 $S(0, 0)$의 선형 결합으로 표현할 수 있다는 뜻이다.

 

우리는 사실 여기서 홀짝성만 판단하는 것이 중요하므로, 홀짝성에 영향을 미치지 않는 $S(i, 0)$과 $S(0, j)$는 제외하고 생각해도 무방하다.

 

즉, 홀짝성에 영향을 미치는 것은 오직 $S(0, 0)$뿐이다.

 

또한, 하나의 스털링 수의 mod 2값을 노드로 보고 서로 직접적으로 영향을 미치는 노드끼리를 간선으로 놓아서 mod2에 대한 점화식을 DAG(Directed Acyclic Graph)로 그려보았을 때, 오른쪽 아래로 향하는 대각선 방향의 간선이나 아래로 향하는 방향의 간선만이 그려짐을 확인할 수 있다.

 

그렇게 그려진 경로(이미지 출처 : https://blog.naver.com/knoj014/222379888141)

 

따라서, $S(0, 0)$이 $S(n, m)$에 몇 번이나 영향을 미치냐는, 곧, 그렇게 그려진 DAG에서 $(0, 0)$에서 시작하여 $(n, m)$으로 가는 모든 경로의 개수와 같다는 사실을 확인할 수 있다.

 

위의 그래프를 적절히 변형시켜서 그려보면 다음과 같다.

 

변형시킨 그래프

 

우리는 아랫방향 간선을 $n-m$번을 쓰고, 대각선 방향 간선을 $m$번을 사용해야 $(0, 0)$에서 $(n, m)$으로 도달할 수 있다는 사실을 알고 있다.

 

저 그래프의 모습을 적절히 잘 변형 시키면 격자상의 경로가 됨을 확인할 수 있다.

 

만약 $m$이 짝수라면 저 경로를 대각선은 세로 선으로 고치고 대각선으로 두번 가는 간선을 하나의 간선으로 고치면 그냥 격자상의 경로가 된다.

 

이때의 경우의 수는 $\binom{n-m+m//2}{n-m}$이 됨을 확인할 수 있다.

 

만약 $m$이 홀수라면 항상 마지막은 대각선 방향의 간선을 타고 끝남을 알고 있기 때문에, 이때의 경우의 수는 $(n-1, m-1)$로 도달하는 경우의 수와 같음을 확인할 수 있다.

 

따라서, $\binom{n-m+(m-1)//2}{n-m}$이 됨을 확인할 수 있다.

 

따라서 이 조합의 홀짝성만 파악하면 충분하다.

 

이 조합의 홀짝성은 다음과 같은 방법으로 판단할 수 있다. 아래 링크를 참고하자.

 

https://math.stackexchange.com/questions/11002/cn-p-even-or-odd

$C(n,p)$: even or odd?

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 3462번 이진 스털링 수
# 조합론, 분할 정복?
'''
접근 방법:
먼저 DP를 이용하여 이진 스털링 수의 규칙을 파악해보자.
점화식은 다음과 같다.
S(n, m) = (mS(n-1, m) + S(n-1, m-1))%2
m = 1, 2 -> 1
m = 3, 4 -> 10
m = 5, 6 -> 1100
m = 7, 8 -> 1000
m = 9, 10 -> 11110000
m = 11, 12 -> 10100000
m = 13, 14 -> 11000000
m = 15, 16 -> 10000000
m = 17, 18 -> 1111111100000000
m = 19, 20 -> 1010101000000000
m = 21, 22 -> 1100110000000000
...
n > m
m을 통해 길이 판단

n = (n-m)%length을 통해서 구해보자.
만약 그 값이 length//2보다 크다면 0이다.
그 값이 length//2보다 작다면?
m = m - length
'''
import sys
input = sys.stdin.readline

def find_length(i):
    if i == 1:
        return 1
    length = 1
    while True:
        if length*2 >= i:
            break
        length *= 2
    return length

def solve(n, m):
    length = find_length(m)
    n = (n-m)%length
    while n > 0:
        length = find_length(m)
        if n >= length:
            n = n%length
        if length == 1:
            return 1
        elif n >= length//2:
            return 0
        else:
            m = m-length
    return 1

for _ in range(int(input())):
    N, M = map(int, input().rstrip().split())
    print(solve(N, M))