서론 きたまさ法은 일본의 경기 프로그래머 wata가 블로그에서 소개한 점화식을 빠르게 계산하는 방법이다. 사실상 companion matrix의 멱승을 구하는 방법과 같지만, 선형 점화식이라는 특성을 활용하여 FFT를 이용, 선형 점화식의 항을 약간 더 빠르게 계산할 수 있다. ( \( O(k^2 \log N) \)에서 \( O(k \log k \log N )\). 따라서 \(k\)가 작은 점화식의 경우 별 의미가 없다. ) 이 테크닉의 이름은 블로그에서 소개한 wata가 붙였는데 きたまさ가 이 방법을 강력하게 주장했다고 한다. 이 きたまさ라는 사람이 한국에서는 잘 알려져 있지 않지만, kitamasa란 핸들을 이용하는 北川宜稔라는 사람으로, 일본에서는 '개미책'이라고 불리는 「プログラミングコンテストチ..