Self Representing Sequence 에 대하여

https://www.acmicpc.net/problem/10220 해당 문제를 풀면서 Self Representing Seq (이하 SRS)에 대해 처음 알게 되었다. 

 SRS의 정의는 A(i) = A가  i번 등장하는 횟수일 때의 수열(0<=i<N )을 말하는 것이다. 예로 들자면 N이 4일때는 (2,0,2,0) , (1,2,1,0) 총 2가지의  SRS가 만들어지게 된다. 

 해당 문제를 처음 풀때는 DP를 사용해서 어케 풀지? 라고 생각하면서 DP 테이블 정의하는데 끙끙 매고 있었는데 도대체 모르겠어서 찾아보니까 DP가 아니라 수학적으로 접근을 해야 하는 문제였다. (문제에서 나온값을 MOD 취하라고 해서 더욱 DP라고 생각을 했었다 ㅠㅠ.. )

 단도직입적으로 말하자면 N이 1,2,3,6인 경우는 0가지 경우, 4인 경우에는 2가지 , 그 외의 경우에는 무조건 1가지 경우 밖에 나오지 않는데 그게 왜 그렇게 되는지 생각을 해보도록 하자..... 는 이해가 안간다 ㅠㅠ 머리가 안 돌아간다 ...  https://en.wikipedia.org/wiki/Self-descriptive_number 와 아래 Doju님이 설명해주신거 읽고 누가 설명좀 해주세여 .... 

 (아래 스크린샷을 통하여 각각의 N에 대한 가능 수열들의 경우를 첨부하였다.)