비네의 법칙에 거듭제곱 분할정복 + 나머지연산으로 해보려다가 루트때문에 오차가 커지는바람에 시원하게 틀리고 돌아왔습니다. 이 문제는 피보나치 수열의 규칙성을 행렬의 제곱형태의 식으로 생각해낼 수 있는지를 보는 문제입니다. 정답부터 말씀드리면 피보나치 수열을 행렬로 바꾸면 이 식이 도출되고, 그 후에 코드로 작성하는 방법은 행렬 제곱 문제와 같은 방식을 사용합니다. using System;using System.Numerics;class Program{ static long P = 1000000007; static void Main() { long n = long.Parse(Console.ReadLine()); long[,] power = Power(n - 1); ..

1. B가 100,000,000,000 까지 될 수 있어서 제곱을 정직하게 시행하면 시간초과가 날 것이다.> 분할정복의 거듭제곱을 이용해야하고, 2. 행렬을 100,000,000,000번 제곱하는 동안 원소가 굉장히 커진다.> 마지막에 1000으로 나머지 연산을 한다는 조건을 이용하여 나머지 연산의 분배법칙을 적용할 수 있다. 3. 분할정복의 거듭제곱을 행렬에도 적용하고, 연산마다 1000으로 나머지 연산을 시행하여 숫자가 과도하게 커지지 않도록 조절한다. 분할정복의 거듭제곱과 나머지연산의 분배법칙은 아래 링크에서 다루고 있다.https://growup.tistory.com/210 알고리즘 문제 관련 수학 모음1) 2026-03-14, 1 ~ 4번 추가 1. 나머지 연산 분배법칙 https://www.a..

이항계수란 무엇인가이렇다고 합니다. 개념은 한 번 읽어보고, 공식을 보면 팩토리얼을 사용하네요. N이 400만인데, 400만의 팩토리얼을 구한다는건 숫자가 너무 커지고, 중간에 어떤 연산을 거쳐서 숫자의 크기를 어느정도 유지해가며 N!을 구해야겠습니다. 1000000007으로 나누는 과정에서의 나머지는 나머지 연산 분배법칙을 활용할 수 있을 것 같습니다. (mod m) = m으로 나눈 나머지라는 뜻. 추가로 페르마의 소정리까지 알아야 이 문제를 해결할 수 있습니다. a가 정수, p가 소수일 때 이 공식이 성립하는데, 여기서 a= N이든 R이 될 수 있고, P는 1000000007입니다. a와 1이 서로소이기 때문에 양 변을 a로 나누면 위에서 배운 내용을 어떻게 적용하냐면 1. 이 공식으로 분모..

1) 1 ~ 4번 추가 / 2026-03-142) 5번 추가 / 2026-03-16 1. 나머지 연산 분배법칙 https://www.acmicpc.net/problem/1629 2. 페르마의 소정리 및 응용 ( 분수 ↔ 지수 )전환 시 활용 가능 https://www.acmicpc.net/problem/11401 3. 분할정복을 사용한 효율적인 거듭제곱 https://www.acmicpc.net/problem/11401 4. 이항계수 https://www.acmicpc.net/problem/11401 5. 피보나치 수를 행렬로 표현 https://www.acmicpc.net/problem/11444

단계별로 문제를 풀면 체스판 다시 칠하기 1은 브루트포스로 풀었는데요. 달라진건 보드판의 크기가 커지고, 시간제한도 줄었다는 점입니다. 누적합 문제를 풀다보면 누적합의 도착점 인덱스의 값에서 시작점 인덱스의 값을 빼면서 빠르게 값을 찾는 패턴이 자주 등장했습니다. 이 문제에도 같은 방식으로 접근하여 row를 기준으로 1차원 누적합을 구했는데 시간초과가 났습니다. 1. 이 문제는 2차원 누적합으로 접근해야합니다. 특정 좌표 x,y에서의 누적합은 0,0부터 x,y를 완전한 보드판으로 만들 때 몇 번 칠해야하는지의 횟수입니다.> 2차원 좌표 (x,y)의 누적합을 초기화 하는 방법은 sum(x,y) = ( 해당 인덱스에서 추가 할 값 ) - ( 그 외 영역의 값의 합) = ( 해당 인덱스에서 추가할 값) + s..

1. 모든 경우의 수를 계산하면 N제곱 > 10만의 제곱으로 너무 오래걸린다.2. 구간 [i,j]의 합은 구간[ 0, j ]의 합 - 구간[ 0, i ]의 합이기도 하다.3. ( 구간[ 0, j ]의 합 - 구간[ 0, i ]의 합 )이 M으로 나누어 떨어진다는 것을 수식으로 나타내면4. 이 수식에서 분배법칙으로 변형하면두 구간의 합을 M으로 나눈 나머지가 같다는 결과를 얻을 수 있습니다. 5. 0번부터 N-1번까지 더해가며 구간의 합을 구하고, M으로 나눈 나머지의 값을 항목마다 갯수를 새샙니다.6. 나머지가 0인 구간은 최종값에 더하고, 각 구간에서 전체중에 순서 상관없이 2개를 뽑는 콤비네이션을 돌려 최종값에 더합니다.> nC2 = ( n*(n-1) ) / 2 입니다. using System.N..