Find the number of such sequence A[0...n-1] that satisfies A[i] equals the number of i in A[0...n-1].
For example , if n = 9, there is only one solution [5, 2, 1, 0, 0, 1, 0, 0, 0]. (We use bruteforce to prove it)
We guess that if n > 6, there is only one solution and it takes the form of [n-4, 2, 1, 0, 0, ..., 1, ...,0, 0].
We want to know whether it is right.
We find that if n=4,there exists two solutions: {1,2,1,0} {2,0,2,0} And if n=5,there exists one solution: {2,1,2,0,0}
A friend of mine -> ast123 have solved this problem.
First,
A[0] mustn't be 0.
You can find that A[1] + A[2] + A[3]... + A[n-1] = (the number of i which doesn't equal 0 in A[1...n-1]) + 1.
And A[1] + A[2] + A[3]... + A[n-1] means the sum of i which doesn't equal 0 in A[1...n-1].
So there must be one 2 and some(may be zero) 1 in A[1...n-1].
Second,
Because there is no number which is bigger than 2 in A[1...n-1], so the number of 1 in A[1...n-1] is <= 2.
At last,
if there is no 1, the [2,0,2,0] is the only solution.
if there is one 1, the [1,2,1,0] and [2,1,2,0,0] is the only two solution.
if there is two 1, the solution takes the form of [n-4, 2, 1, 0, 0, ..., 1, ...,0, 0] when n > 6.
It's easy to prove that there's no other situation.