파이썬으로 무한 수열에서 생성된 벡터의 스칼라 곱 구하기

문제 정의

세 개의 정수 c, m, n이 주어졌다고 가정해 보겠습니다. 우리는 다음 규칙을 따르는 무한 수열을 생성해야 합니다.

첫 번째 값은 0
두 번째 값은 c
세 번째 값부터는 k_i = (k_i-2 + k_i-1) mod m

수열을 k_2n+1 항까지 생성한 뒤, 수열의 세 번째 값부터 시작하여 연속된 두 값을 하나의 2차원 벡터의 x좌표와 y좌표로 사용해 총 n개의 벡터를 만듭니다.

그다음 집합 S를 정의합니다. S의 각 원소는 벡터 i와 벡터 j의 스칼라 곱(내적)이며, 조건은 1 <= i, j <= n 이고 i != j 입니다. 최종적으로 집합 S에 존재하는 서로 다른 잉여(residue) 값의 개수를 구하면 됩니다. 값이 너무 커지지 않도록 m으로 나눈 나머지를 사용합니다.

입출력 예시

입력이 5, 6, 4라면 출력은 3입니다.

생성된 수열: [0, 5, 5, 4, 3, 1, 4, 5, 3, 2]
만들어진 벡터: (5, 4), (3, 1), (4, 5), (3, 2)
벡터들의 스칼라 곱을 mod 6으로 계산했을 때 집합 S에는 서로 다른 잉여 값이 3개뿐입니다.
따라서 결과는 3 mod 6 = 3이 됩니다.

풀이 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

n이 1이면 0을 반환합니다.
그렇지 않은 경우:
- 크기가 2n+2인 리스트 temp_arr를 0으로 초기화합니다.
- temp_arr[0] := 0, temp_arr[1] := c 로 설정합니다.
- 빈 리스트 arr2를 준비합니다.
- i를 2부터 2n+2까지 반복하면서 temp_arr[i] := (temp_arr[i-1] + temp_arr[i-2]) mod m 을 계산합니다.
- i를 2부터 2n-2까지 2씩 증가시키며 반복합니다.
  - temp := (temp_arr[i] * temp_arr[i+2] + temp_arr[i+1] * temp_arr[i+3]) mod m 을 계산해 arr2에 추가합니다.
  - temp := (temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) mod m 을 계산해 arr2에 추가합니다.
- 마지막으로 temp := (temp_arr[2n-2] * temp_arr[2n] + temp_arr[2n-1] * temp_arr[2n+1]) mod m 을 계산해 arr2에 추가합니다.
- arr2에서 중복 항목을 제거한 뒤 그 크기를 반환합니다.

파이썬 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

def solve(c, m, n):
    if (n == 1):
        return 0
    else:
        temp_arr=[0 for i in range(2 * n+2)]
        temp_arr[0] = 0
        temp_arr[1] = c
        arr2 = []
        for i in range(2, 2 * n+2):
            temp_arr[i] = (temp_arr[i - 1] + temp_arr[i - 2]) % m
        for i in range(2, 2 * n-2, 2):
            temp = (temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) % m
            arr2.append(temp)
            temp = (temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) % m
            arr2.append(temp)
        temp = (temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n- 1] * temp_arr[2 * n+1]) % m
        arr2.append(temp)
        arr2 = set(arr2)
        return len(arr2)

print(solve(5, 6, 4))

입력

5, 6, 4