Let's divide this queue into to 2 parts: 1... k and k + 1... n.
It's obvious that pi ≤ k while i ≤ k, pi > k while i > k.
So the answer to the part of pk + 1... n is (n - k)n - k.
Image a tree with k vertexes. The number of those trees is kk - 2. (Cayley trees)
Choose a vertex to be root, there are k ways.
Set pi = fatheri in the tree. And for the root, set proot = 1.
It's easy to find p1... k satisfied the problem.
So answer is kk - 1(n - k)n - k.
Maybe kk - 1(n - k)n - k?
ADD: It's OK now.
Thx, I made a mistake just now. :)
i cann't understand the k^(k-1) ?? if input is 3 3 so all of the number are e.g:(p1,p2,p3),(2,1,1),(2,3,1),(3,2,1),(3,3,1),(3,1,1). can you tell me some else?
Because k <= 8, it could be solved by backtrack too.
i cann't understand the k^(k-1) ?? if input is 3 3 so all of the number are e.g:(p1,p2,p3),(2,1,1),(2,3,1),(3,2,1),(3,3,1),(3,1,1). can you tell me some else?
Actually, first number in a triple can be equal to one. Therefore, we have got (1,1,1), (1,3,1), (1,1,2), (2,1,1), (2,3,1), (2,1,2), (3,1,1), (3,3,1), (3,1,2). That is, answer=9.
thank you very much~ ^-^
I'm confused about whether (1,1,1),(1,3,1),(1,1,2) satisfy the restriction 3: "When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house."?
ohh...from house 1 to house 1, though we have no move, that's also 1 step.