====== 여러가지 수학 정리 ======
  * 따로 카테고리를 만들정도로 중요하거나 웰노운도 아니면서 다른 정리들과 연관되어있지도 않은 정리들을 그냥 모아놓은 페이지.. (그뭔씹?)

===== 거듭제곱수의 합 / 파울하버의 공식 (Faulhaber's Formula) =====
  * $\sum _{k=1}^{n}k^{p}= 1^p + 2^p + 3^p + \cdots + n^p$ 을 구하는 방법.
    * n이 p보다 많이 큰 경우만 생각해보자. n이 작으면 그냥 각각 항을 계산해서 푸는 O(nlogp)방법으로 처리될거 같다.
  * 대충 p=3 까지는 일반식이 잘 알려져있다.
    * $ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = \frac{n^2 + n}{2} $
    * $ {\displaystyle 1^{2}+2^{2}+3^{2}+\cdots +n^{2}={\frac {n(n+1)(2n+1)}{6}}={\frac {2n^{3}+3n^{2}+n}{6}}} $
    * $ {\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +n^{3}=\left[{\frac {n(n+1)}{2}}\right]^{2}={\frac {n^{4}+2n^{3}+n^{2}}{4}}} $
  * 그 이상의 p에 대해서도 일반 공식은 존재한다. 이것은 파울하버의 공식 ([[wp>Faulhaber's formula]]) 으로 구할 수 있다. 위키 링크에 있는 식을 그대로 옮겨적으면 이렇게 된다
    * $ {\displaystyle \sum _{k=1}^{n}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}} $ 
    * 이렇게도 쓸수 있다고 한다
      * $ {\displaystyle \sum _{k=1}^{n}k^{p}={\frac {1}{p+1}}\left(B_{p+1}(n+1)-(-1)^{p+1}B_{p+1}\right)={\frac {1}{p+1}}\left(B_{p+1}(n+1)-B_{p+1}(1)\right).} $
    * 하지만 이것을 계산하려면 베르누이 수를 계산해야 하고.. 이래저래 간단치가 않다
      * n번째 베르누이 수를 계산하는 알고리즘의 시간복잡도는 O(n^2log^2n)이라고 한다. ([[https://ko.wikipedia.org/wiki/%EB%B2%A0%EB%A5%B4%EB%88%84%EC%9D%B4_%EC%88%98|위키백과]])
      * 정 안되면.. p의 최대 입력범위까지의 베르누이 수의 값들을 코드에 다 때려박아놓고 짜는 방법도 가능하긴 하다..오프라인 전처리!!
  * 코드포스에 올라온 adamant의 [[https://codeforces.com/blog/entry/60756|Counting sums of powers]] 글에 따르면, 이걸 풀기 위해서 베르누이 수를 이해하고 기억할 필요 없이, 그냥 생성함수를 이용해서 계산하면 된다고 한다. FFT를 잘 쓰고 어찌저찌 하면 O(plogp)에 계산 가능하다는 것 같다는데 제대로 이해는 못했다.
  * 파울하버의 공식을 사용하지 않고 푸는 방법을 찾아보자.
  * 좀 더 이해하기 쉬운 방법은 [[wp>Faulhaber's formula|파울하버의 공식 위키 페이지]] 구석에 언급된 Pascal's identity 를 이용하는 것이다
    * $ {\displaystyle {\begin{aligned}(n+1)^{k+1}-1&=\sum _{m=1}^{n}\left((m+1)^{k+1}-m^{k+1}\right)\\&=\sum _{p=0}^{k}{\binom {k+1}{p}}(1^{p}+2^{p}+\dots +n^{p}).\end{aligned}}} $ 
    * 여기서 $ S(p) = 1^{p}+2^{p}+\dots +n^{p} $ 이라 하면, $ S(k) = \frac{(n+1)^{k+1}-1-\sum _{p=0}^{k-1}{\binom {k+1}{p}}S(p)}{k+1} $ 로 쓸수 있다.
    * S(p)를 구하기 위해서는 DP를 이용해서 S(1),S(2), ..., S(p)까지 차례로 구해 나가면 된다. 시간 복잡도는 O(p^2)
    * 관련 코드는 [[ps:problems:boj:1492]] 참고.
  * 다른 접근 방법은, $\sum _{k=1}^{n}k^{p}= 1^p + 2^p + 3^p + \cdots + n^p$ 은 결국 n에 대한 (p+1)차식으로 표현된다는 것을 이용하는 방법이다.
    * $f(x) = \sum _{k=1}^{x}k^{p}$ 라고 하면, f(1), f(2), ...,f(p+2)의 값을 다 구한 다음에, 이걸 갖고 [[ps:라그랑주 보간법]]을 사용해서 f(n)을 구해버릴수 있다.
    * f(1), f(2), ...,f(p+2)를 계산하는 것은 O(plogp)이다. 그리고 라그랑주 보간법을 적용하는 것은 O(p). 총 O(plogp)에 구할수 있다!!
    * [[ps:라그랑주 보간법]]을 굳이 짜기 싫다면, [[ps:벌캠프-매시 알고리즘]]을 사용할수도 있다. k차 다항식은 항상 크기 k의 선형점화식으로 바꿀수 있기 때문이다. 하지만 이 방법은 점화식을 찾는데 O(p^2)이 걸리고, n번째 값을 찾는데에는 O(p^2logn)이 걸려서 효율적이지는 못하다.
  * 결국, 쓰기 가장 편하면서 효율적인것은 라그랑주 보간법이다. 이 방법을 사용하자
  * 관련 문제
    * [[ps:problems:boj:1492]]: p≤50, O(p^2) DP로도 순식간에 풀린다
    * [[ps:problems:boj:25974]]: p≤1000, O(p^2) DP로도 270ms 정도에 풀리긴 한다
    * [[ps:problems:boj:27293]]: p≤100000, O(plogp)의 라그랑주 보간법을 써야만 8000ms대에 통과가능

===== 프로베니우스의 동전 문제 =====
  * [[wp>coin problem]], [[https://m.blog.naver.com/sluggeryck/220666650939|프로베니우스의 동전 문제 - 레프네 약방]]
  * 대충 핵심은
    * P원짜리 동전과 Q원짜리 동전을 무한개 갖고 있고, P와 Q가 서로소라면, 두 동전을 이용해서 얼마를 초과하는 금액은 모두 만들수 있다.
    * 그 '얼마', 즉 만들수 없는 최대 금액을 Frobenius number 라고 부르는데, 이 값은 PQ-P-Q 이다.
      * P,Q가 서로소가 아니면, 즉 gcd(P,Q)=g>1 이라면, g의 배수만 만들수 있다. ([[ps:확장_유클리드_알고리즘#베주 항등식]] 참고)
      * 이때도 비슷한 논리를 적용하면, g*(P/g-1)*(Q/g-1) 이상의 g의 배수는 모두 만들수 있다.
  * 원래 문제는 동전 n개에 대한 문제인데, n이 3 이상일때는 closed form으로 답이 안나온다.
  * 관련 문제로는 [[ps:problems:boj:1214]]나 [[ps:problems:boj:2839]]가 있긴 한데, 사실 이걸 몰라도 충분히 효율적으로 풀수 있다..


===== Landau's Theorem =====
  * [[https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets]]
  * n팀이 참가한 리그전의 결과가 각 팀의 승리수로 주어졌을때, 그게 valid한 결과인지 아닌지를 판별할수 있는 공식.
    * 좀더 포멀하게는 토너먼트 그래프에서 각 노드의 outdegree의 시퀀스라고 표현할수도 있다.
  * 모든 팀의 점수(=승리수)의 합이 C(n,2) 가 되어야 하는 것은 자명 (경기수 = 승리수여야 하니까)
  * 여기에 추가로, 모든 i에 대해서 최하위 i팀의 점수의 합이 C(i,2) 이상이라면 valid한 결과이다.
  * 이 정리를 이용하면 score sequence 의 validity를 O(n) 에 구할수 있다.
  * 관련문제는 [[ps:problems:boj:13560]]

===== Hertzsprung's problem =====
  * 1~N까지의 숫자로 만들어지는 퍼뮤테이션 중에서 인접한 두 수의 차가 모두 2이상인 퍼뮤테이션의 갯수 
  * 다음 점화식으로 계산 가능 ([[https://oeis.org/A002464]])
    * If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4).
  * [[ps:체스_기물_배치#Hertzsprung's problem]] 에 좀더 자세히 설명.


===== Langford pairing =====
  * 듀들리 랭퍼드가 1958년에 발표한 문제. 
    * 참고: [[wp>Langford pairing]], [[https://susam.net/blog/langford-pairing.html]]
  * 1~N까지의 숫자들을 두번씩 사용해서 만든 시퀀스 중에서, 두개의 1 사이에는 숫자가 1개 있고, 두개의 2 사이에는 숫자가 2개 있고,.. 두개의 N사이에는 숫자가 N개 있는 시퀀스.
    * 예를들면
      * N=3일때: 2,3,1,2,1,3
      * N=4일때: 4,1,3,1,2,4,3,2
  * 관련 정리
    * 수열의 존재 여부: n=4m 또는 n=4m+3 인 경우, 랭퍼드 수열이 존재한다 (필요충분조건)
      * 증명은, 홀수 인덱스에 들어갈 숫자의 갯수와, 짝수 인덱스에 들어갈 숫자의 갯수를 나눠서 세어보는 방식으로 필요조건을 증명하고. 충분조건은 아래 방식대로 구성적으로 해를 제시해서 증명한다
    * 한개의 수열을 찾는 구성적인 방법
      * [[https://susam.net/blog/langford-pairing.html]] 참고
      * 코드로 옮기면
        * <dkpr py>
def langford_sequence(n):
    if n % 4 in (1, 2):
        raise ValueError('No Langford sequence exists.')
    x = (n + 3) // 4
    a, b, c, d = 2 * x - 1, 4 * x - 2, 4 * x - 1, 4 * x
    p, q = range(1, a, 2), range(2, a, 2)
    r, s = range(a + 2, b, 2), range(a + 1, b, 2)
    l = [*reversed(s), *reversed(p), b, *p, c, *s]
    if n % 4 == 0:
        return l + [d, *reversed(r), *reversed(q), b, a, *q, c, *r, a, d]
    else:
        return l + [a, *reversed(r), *reversed(q), b, a, *q, c, *r]
</dkpr>
    * 해의 갯수
      * 갯수를 구하는 공식은 아직 없다. 현재까지 밝혀진 값들은 [[https://oeis.org/A014552]]에 있다.
  * Skolem sequence 는 거의 비슷한데 0부터 N-1까지의 숫자를 사용해서 만든 수열이다.
    * 역시 N-1 이 4m 또는 4m+3일때만 존재한다.
    * 한개의 해를 구하기 위해서는, N-1의 랭퍼드 수열을 만든 다음 0 0 을 끝에 붙여주기만 하면 된다.
  * 관련 문제
    * [[ps:problems:boj:24507]]