파이썬에서 무한 시퀀스에서 생성된 벡터의 스칼라 곱을 찾는 프로그램

<시간/>

세 개의 정수 c, m, n이 주어졌다고 가정합니다. 첫 번째 값은 0, 두 번째 값은 c, 세 번째 값부터는 ki =(ki-2 + ki-1) mod m과 같은 무한 시퀀스를 생성해야 합니다. 항목 k2n+1까지 시리즈의 모든 값을 생성해야 합니다. 이제 시리즈의 값에서; 시퀀스에서 두 개의 연속 값을 2차원 벡터의 x 및 y 좌표로 사용하고 n개의 벡터를 생성합니다. 주의할 점은 세 번째 값부터 순서대로 값을 사용한다는 것입니다. 각 값이 벡터 i와 벡터 j의 스칼라 곱인 또 다른 집합 S가 있습니다. 여기서 1 <=i, j <=n 및 i !=j입니다. 집합 S에서 서로 다른 잔기의 수를 찾아야 합니다. 값이 매우 크면 m으로 수정합니다.

따라서 입력이 5, 6, 4와 같으면 출력은 3이 됩니다.

생성된 시퀀스는 [0, 5, 5, 4, 3, 1, 4, 5, 3, 2]입니다.

벡터는 (5, 4), (3, 1), (4, 5), (3, 2)입니다.

벡터의 스칼라 곱에서 집합 S에는 3개의 나머지 값 mod 6만 있습니다.

따라서 결과는 3 mod 6 =3입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n이 1과 같으면
- 0을 반환
그렇지 않으면
- temp_arr:=0으로 초기화된 크기 2*n+2의 새 목록
- temp_arr[0] :=0
- temp_arr[1] :=c
- arr2 :=새 목록
- 2 ~ 2 * n+2 범위의 i에 대해
  - temp_arr[i] :=(temp_arr[i - 1] + temp_arr[i - 2]) 모드 m
- 2 ~ 2 * n-2 범위의 i에 대해 2만큼 증가, do
  - temp :=(temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) 모드 m
  - arr2 끝에 temp 삽입
  - temp :=(temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) 모드 m
  - arr2 끝에 temp 삽입
- temp :=(temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n-1] * temp_arr[2 * n+1]) 모드 m
- arr2 끝에 temp 삽입
- 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