https://www.acmicpc.net/problem/21274
문제 보자마자 너무 쉬운데? 생각되서 잡았다가 x도 non-decreasing이여야 한다는걸 깨닫고 그대로 좌절중
FFT+분할정복으로 일반적인 x에 대해서 구한뒤 포함배제로 x가 decreasing되는 부분 체크해서 없애주려 했는데 포함배제가 몬가 잘 안됨
으음... 내 자신이 조합론에 약하다는걸 뼈저리게 느끼는중
그들만의 웰노운 문제 같아서 꼭 풀고 싶은데 더이상 어떻게 할지 감이 안온다 푼사람들 힌트좀
루3이 쉬워보이는거면 ㄷㄷ
첫 줄부터 재밌네 ㅋㅋ 우리만의 그뭔씹 웰노운이니 너네들도 잡숴보세요 ㅋㅋ
문제 보자마지 너무 쉬운데?(루비3) - dc App
말했잖어 x도 증가해야되는거 못봤다고 x증가 조건 없으면 쉬운문제 맞음 그런데 x 증가해야된다고 하니 모르겠음…
맞힌 사람 5명 밖에 없어요 ㅋㅋㅋㅋㅋ
맞힌사람중 한명이 여기 파딱이라 글 적어봄 대놓고 닉네임 말할수는 없잖어
같은 거 개수 조건 없을 때부터 풀어보셈. 포함배제 쪽 접근은 아니고 A값이 작다는 걸 이용함
사실 그거도 잘 모르겠음. DP로 푸려니 너무 크기가 크고, (1+x+x^2+x^3+....)을 무한히 곱하고 25만 이하의 차수만 보는건가 생각했는데 뭔가 잘 안됨. 그래서 x가 decreasing하는 개수를 잘 세는 포함배제라고 생각했는데 그것도 아니라고 하면 음.... 모르겠음 ㅠ
계단 모양에서 경로의 수를 센다고 생각해보면 계단을 작은 계단 2개와 직사각형으로 나눌 수 있어서, 경로도 부분으로 나눌 수 있음. 이렇게 접근하면 좀 방법이 보일듯
아…! 뭘 말하는지 대충 알것같음 함 짜보겠음 힌트 ㄱㅅ