[일반] 피붕이 처음으로 다이아 풀었다

[Sigmoid(powderscript)]

13716번: 피보나치 수열처럼 보이지만... (acmicpc.net)

48414585번 소스 코드 (acmicpc.net)

이거 1~2년전에 naive O(nk) 로 풀었을때 대가리 깨지고 최근에 PS 다시 시작하면서 건들여봄.

DP는 거의 안해봐서 안보이길래 노가다 해보고 머가리 굴려보니까 운좋게도 O(k^2+logn) 가 보이더라

플레1 셋다 밀러라빈이랑 FFT 기초로 날먹한거였는데 제대로 뭐 해결한거 같아서 ㅈㄴ 뿌듯함 ㅎㅎ

[익명(222.109)]

오 벌레캠프 안써도 풀리는 문제였군요