The answer is all $n$ prime or $n=2^k$. Claim: $n=p$ works. Proof: Consider a directed tree where on layer $j$ $(j< \lceil \log_2(m)\rceil)$, there are exactly $\lceil \frac{n}{2^{j-1}} \rceil - \lceil \frac{n}{2^j} \rceil$ nodes. Map nodes and note every single digraph is representable as a polynomial. $n=2^k$ works because I can set $P(x)=2x$ then I can see $Im(P^m(x), 2^k)$ is precisely the residues divisible by $2^m$. Suppose $n=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Let $f(P(x), t)$ be the number of distinct residues mod $t$ that $P(x)$ reaches. Claim: $$f(P(x),n)=\prod\limits_{j=1}^k f(P(x), p_j^{a_j})$$ Proof: Chinese Remainder Theorem. Let $a_{m,t} = f(P^m(x), p_t^{a_t})$. Claim: $a_{m,t} > a_{m,t+1}$ unless $a_{m,t}=1$. Proof: if $a_{m,t}=a_{m,t+1}$ then $Im(P^m(x)) \cap \mathbb{Z}_{p_t^{a_t}}$ doesn't change as $m$ grows, which implies $a_{m,t}$ is constant as $m$ grows, and $a_{m,t}=1$ when $2^m>n$. We need $$\prod\limits_{j=1}^k a_{j,m} = \lceil \frac{n}{2^j} \rceil$$ In fact, we just need $a_{j,x} a_{j,y} = \lceil \frac{a_{j-1,x} a_{j-1,y}}{2} \rceil $. Consider the sequence in reverse. In the end, $a_{T,x}=a_{T,y}=1$. WLOG $a_{T-1,x}>1$ and $a_{T-1,y}=1$. Let $m$ be the maximal integer such that $a_{m,y}>1$. Then $a_{m,y}a_{m,x} > 2a_{m+1,y}a_{m+1,x}$, absurd! Now consider the case where $n=p^t$ where $t\ge 2$. I claim there are no solutions when $p$ is odd. We first settle the case where $t\ge 3.$ Suppose $p\nmid P'(x)$, then I claim $P(x), P(x+p), \cdots, P(x+p^t-p)$ are injective mod $p^t$. Note if $P(x)=\sum\limits_{j=1}^n a_jx^j$ (we may assume 0 is the root) \begin{align*} & P(x+cp^e)-P(x) \\ &= \sum\limits_{k=1}^n a_k ((x+cp^e)^{k}-x^k)\\ &\equiv \sum\limits_{k=1}^n a_k kx^{k-1} cp^e (\bmod\; p^{2e})\\ &\equiv cp^eP'(x) (\bmod\; p^{2e}) \end{align*} Which does not vanish mod $p^t$. On the other hand, if $p\mid P'(x)$, then $P(x),P(x+p),\cdots,P(x+p^t-p)$ only take on at most $p^{t-2}$ values because $P(x)\equiv P(x+p^{t-1}) (\bmod\; p^t)$ Call a residue $r (\bmod\; p)$ strange if there exists $x$ such that $P(x)\equiv r(\bmod\; p)$ but for all such $x$, $p\mid P'(x)$. Note for all nonstrange residues $r$, $P(x)$ either hits all or none of the $r(\bmod\; p)$ residues $(\bmod\; p^t)$. \vspace{1cm} \textbf{Claim.} There are exactly $\frac{p-1}{2}$ non-strange residues mod $p$ in $Im(P)$. \vspace{1cm} \textbf{Proof of Claim.} If there are more than $\frac{p-1}{2}$ non-strange residues, then the number of residues in $Im(P)$ mod $p^t$ is at least $\frac{p+1}{2} p^{t-1} > \frac{p^t+1}{2}$, since each strange residue $r$ mod $p$ satisfies $r+kp (0\le k<p^{t-1})$ are all in $Im(P)$ in $\mathbb{Z}_{p^t}$. If there are at most $\frac{p-3}{2}$ non-strange residues in the image of $P$, then all other residues contribute at most $p^{t-2}$ elements. Therefore, $$Im(P) \le \frac{p-3}{2}p^{t-1} + p\cdot p^{t-2} < \frac{p^t+1}{2}$$absurd. call $r_1,\cdots,r_{\frac{p-1}{2}}$ such that $$P(x_i)\equiv r_i (\bmod\; p)$$ (Where $x_1,\cdots,x_{\frac{p-1}{2}}$ are distinct mod $p$, and so are $r_1,\cdots, r_{\frac{p-1}{2}}$) For all $1\le i\le \frac{p-1}{2}$. Consider the remaining $\frac{p^{t-1}+1}{2}$ residues in $Im(P) \cap \mathbb{Z}_{p^t}$ whose residue mod $p$ is disjoint with $\{r_1,\cdots,r_{\frac{p-1}{2}}\}$ (i.e. strange mod $p$) Consider residues $z_1,\cdots,z_k$ such that $p|P'(z_i)$. Each includes at most $p^{t-2}$ residues to $Im(P)$, so $k\ge \frac{p+1}{2}$ if $p$ is odd. This implies $\{x_1,\cdots,x_{\frac{p-1}{2}}\} \sqcup \{z_1,\cdots,z_{\frac{p+1}{2}}\} = \{0,\cdots,p-1\}$ Therefore, $\{P(z_1),\cdots,P(z_{\frac{p+1}{2}})\} \cap \{r_1,\cdots,r_{\frac{p-1}{2}} \} = \emptyset$ because otherwise remainder when the number of residues mod $p^t$ is divided by $p^{t-1}$ is at most $\frac{p-1}{2} p^{t-2}.$ Furthermore, for each $r_i$ there exists a unique $x_i$ such that $P(x_i)\equiv r_i(\bmod\; p)$ We further consider $\nu_p(P'(x))$. Suppose $\nu_p(P'(x))=1$, then $P(x), P(x+p^2), \cdots, P(x+p^t-p^2)$ forms all residues $\equiv P(x)(\bmod\; p^3)$ in $\mathbb{Z}_{p^t}$, which is exactly $p^{t-2}$. Therefore, we need to find the number of distinct residues mod $p^2$ in $\{P(x),P(x+p),\cdots,P(x+p^2-p)\}$, call $C$, then the number is just $Cp^{t-3}$. Note $$P(x+cp)-P(x)\equiv cpP'(x)+\frac{c^2p^2}{2} P''(x) \equiv p^2 \left(cm+\frac{c^2}{2} P''(x)\right) (\bmod\; p^3 )$$ If $ \nu_p(P'(x))=1$ and $p\mid P''(x)$, then $cm+\frac{c^2}{2}P''(x)$ hits all residues mod $p$, so $P(x+cp)_{0\le c<p^{t-2}}$ covers $p^{t-2}$ residues. Call $x$ a type A strange residue. If $\nu_p(P'(x))=1$ and $p\nmid P''(x)$, then $cm+\frac{c^2}{2}P''(x)$ covers exactly $\frac{p+1}{2}$ residues mod $p$, so $P(x+cp)_{0\le c<p^{t-2}}$ hits $\frac{p+1}{2}p^{t-3}$ residues mod $p^t$. Call $x$ a type B residue. Otherwise, $\nu_p(P'(x))\ge 2$, and $P(x)\equiv P(x+p^{t-2})(\bmod\; p^t)$ (if $t\ge 4$), so $P(x+cp)_{0\le c<p^{t-2}}$ hits at most $p^{t-3}$ residues mod $p^t$. Call $x$ a type $C$ residue. (If $t=3$, $P(x+cp)-P(x)\equiv (cp)^2 P''(x)/2 (\bmod\; p^3)$ which means $P(x+cp)$ hits at most $\frac{p+1}{2} p^{t-3}$ residues mod $p^t$ so we take this as a type B residue) Let $a,b,c$ be the number of type $A,B,C$ residues among $z_1,\cdots,z_{\frac{p+1}{2}}$. We have $$a+b+c=\frac{p+1}{2}$$ $$p^{t-2}a + \frac{p+1}{2} p^{t-3} b + p^{t-3} c > \frac{p^{t-1}}{2}$$ The above equation holds because the image contains $\frac{p^{t-1}+1}{2}$ residues, but there is overcounting and each type C residue contains AT MOST (not necessarily exactly) $p^{t-3}$ residues mod $p$. First, note if $a\le \frac{p-3}{2}$, then $$p^{t-2}a + \frac{p+1}{2} p^{t-3}b + p^{t-3}c \le p^{t-3} \left(pa+\frac{p+1}{2} \left(\frac{p+1}{2}-a\right) \right) = p^{t-3} \left(\left(\frac{p+1}{2}\right)^2 + \frac{p-1}{2} a \right)$$ $$\le p^{t-3} \frac{p^2-p+2}{2} < \frac{p^{t-1}}{2}$$ Hence $a\in \{\frac{p-1}{2}, \frac{p+1}{2}\}$ If $a=\frac{p-1}{2}$, then either $b=1,c=0$ or $b=0,c=1$. If $c=1$, then $p^{t-2} \frac{p-1}{2} + p^{t-3} > \frac{p^{t-1}}{2}$, which is impossible for $p\ge 3$. Hence $c=0$. WLOG, $p\mid P''(z_1)$, and $z_2,\cdots,z_{\frac{p+1}{2}}$ are all type A. Say $P(z_i)\equiv y_i (\bmod\; p^2)$. This means the (strange mod p) residues $\equiv y_i(\bmod\; p^2)$ in $\mathbb{Z}_{p^t}$ are all in $Im(P)$ in $\mathbb{Z}_{p^t}$. If $\left|\{y_2,\cdots,y_{\frac{p+1}{2}}\}\right| < \frac{p-1}{2}$, then $Im(P)$ mod $p^t$ contains at most $\frac{p-3}{2}p^{t-2}+\frac{p+1}{2}p^{t-3}$ or $\frac{p-1}{2}p^{t-2} < \frac{p^{t-1}}{2}$, absurd. Therefore, the $y_i$'s are pairwise distinct mod $p^2$. This means the number of the strange residues mod $p^t$ is exactly ( no inequality here) $\frac{p-1}{2}p^{t-2} + \frac{p+1}{2}p^{t-3} \ne \frac{p^{t-1}+1}{2}$ The other case is $a=\frac{p+1}{2}$. Define $y_i$ as above, then the number of strange residues mod $p^t$ is exactly $$|\{y_1,\cdots,y_{\frac{p+1}{2}}\}| \cdot p^{t-2}\ne \frac{p^{t-1}+1}{2}$$ Now we deal with the case $t=2$. Note that $$f(x),f(x+p),\cdots,f(x+(p-1)p)$$ Is either constant or is exactly the set of residues in $\mathbb{Z}_{p^2}$ that are $\equiv r(\bmod\; p)$. Call a full set $(x,x+p,\cdots,x+(p-1)p)$ where $0\le x<p$ and a singleton any residue mod $p$. Note the image of a full set is either a singleton or another full set. Therefore, if $x_i$ is the number of full sets in the image of $P^i$ mod $p^2$, and $y_i$ is the number of singletons in the image of $P^i$ mod $p^2$ that doesn't appear in a full set, then $x_i+y_i \le x_{i-1}+y_{i-1}$ since there can be overlaps. By counting, $px_i+y_i=\lceil \frac{p^2}{2^i} \rceil$ If $M_i=\lceil \frac{p^2}{2^i} \rceil > p$ then $x_i=\lfloor \frac{M_i}{p}\rfloor, y_i=R(M_i,p)$ (where R denotes remainder) Consider the largest $n$ such that $M_n>p$. Then $\frac p2<M_{n+1}\le p$ so $x_{n+1}=0$ and $x_{n+1}+y_{n+1}=M_{n+1}$. If $M_{n+1}=p$ then $x_n=1, y_n=p-1$ is forced. Otherwise, $x_n=1, px_n+y_n \in \{2M_{n+1},2M_{n+1}-1\}$ and $y_n\le 2M_{n+1}-p$, which implies $M_{n+1}=p-1$. This implies $x_n+y_n\ge p-1, x_0+y_0=p$ and for all $0<m<n$, $$\lceil \frac{M_m}{p}\rceil + R(M_m,p) \in \{p-1,p\}$$ Case 1: $M_{n+1}=p-1$. This means $(x_n,y_n)=(1,p-2)$ is forced. This means while $R(y_m,p)>\frac p2$, $x_{m-1}=2x_m+1, y_{m-1}\in \{2y_m-p, 2y_m-p-1\}$. Then $x_{m-1}+y_{m-1}\in \{2(x_m+y_m)-(p-1), 2(x_m+y_m)-(p-1)-1\}$, so $x_{m-1}+y_{m-1}=p-1$ and $y_{m-1}=2y_m-p$. This means I will reach $(2^t-1, p-2^t)$ where $2^{t+1}>p$, which means $2^t-1 > \frac p2 - 1$ and must be at least $\frac{p-1}{2}$. We can also show $(x_1,y_1)=(\frac{p-1}{2}, \frac{p+1}{2})$ so $2^t-1=\frac{p-1}{2}, p-2^t=\frac{p+1}{2}$. Adding the two equations up yields $p-1=p$, absurd! Case 2: $M_{n+1}=p$. This means $$\lceil \frac{M_m}{p} \rceil + R(M_m,p)=p$$ For all $0<m<n$. We start with $(x_n,y_n)=(1,p-1)$, then while $y_m>\frac p2, (x_{m-1},y_{m-1})=(2x_m+1, 2y_m-p-1)$. This implies $(x_{n-t}, y_{n-t})=(2^{t+1}-1, p+1-2^{t+1})$ for all $y_{n-t+1} > \frac p2$ However, observe when $y_{n-t}<\frac p2, y_{n-t}=0$ and $n-t=0$. Therefore, $p=2^k-1$ for some $k$. Now one can show $P(a)\equiv P(b) (\bmod\; p^2) \rightarrow p\mid a-b$ (the converse is not true). A careful analysis of the equality case suggests that there is some "duplication" of singletons, so equality cannot occur.

Here is a version of the solution which might look a little bit less frightening: Part 1: The existence case: First of all, note that for $n=2^k$ we can just take $P(x)=2x$ and for $n=p$ prime we can realize any function $P:\mathbb{F}_p \to \mathbb{F}_p$ as a polynomial with integer coefficients (e.g. by Lagrange), so we just need to check that a set-theoretic function $P:\{0,1,\dots,p-1\} \to \{0,1,\dots,p-1\}$ with the desired properties exists, which is easy: Take e.g. $P(x)=\left\lfloor\frac{x}{2}\right\rfloor$. Part 2: The CRT case a.k.a. the case of at least two prime factors: Now the set-theoretic map still works for general $n$, but what breaks down is the fact that every such map can be realized by a polynomial with integer coefficients. Checking the first non-trivial case $n=6$, one arrives at considering the values of $P$ modulo $2$ and modulo $3$. By CRT, the number of values of $P$ modulo $6$ is just their product. Now can $P$ and its iterates assume $3,2,1,1,\dots$ values modulo $6$? Well, then $3=a \cdot b$ where $a$ is the number of residues of $P$ modulo $2$ and $b$ the same modulo $3$. But then of course $a=1, b=3$ and so $P$ is bijective modulo $3$, which is a contradiction since then all its iterates would be bijective as well and the number of residues would never drop to $1$. So $n=6$ doesn't work and it looks like we have found a promising way to deal with composite $n$. Well, to actually apply CRT in a meaningful way, we need $n=ab$ with $a,b>1$ coprime, i.e. $n$ is not allowed to be a prime power. Well, then let us assume this. Now as before, by CRT the number of residues of $P$ modulo $n$ is just the product of those modulo $a$ and modulo $b$. For $n=6$, we started by considering the first entry in our sequence, but this is not too promising in general, since it depended on the number of residues being a prime, which was somewhat special. Instead, we should be looking at the last entry, more precisely, the last time when $P^m$ has more than one residue modulo both $a$ and $b$ (include $m=0$ for convenience to make sure that this happens at some point). Now in the next step, one of the numbers, say the one modulo $a$, drops down from at least $2$ to exactly $1$, i.e. it drops by a factor of at least $2$. The number modulo $b$ has to decrease as well (otherwise, if $P^m$ and $P^{m+1}$ have the same number of residues modulo $b$, then $P^{m+2},P^{m+3},\dots$ have the same number of residues as well, but this number is larger than $1$ by assumption, which is absurd). In total, the number of residues modulo $n$, which is the product of the two, has to decrease by more than a factor of $2$, which is incompatible with it being part of the sequence $\left\lceil \frac{n}{2^m}\right\rceil$ (which always drops by at most a factor of $2$). So we win if $n$ has at least two prime factors, leaving us with the case of $n=p^k$ with $p \ge 3, k \ge 2$. Part 3: The Hensel case a.k.a. the prime power case: Again, let us begin by considering the simplest non-trivial case which is $n=9$. Here we want the sequence to be $4,2,1,1,\dots$. Here we have no chance of applying CRT, so it is not clear what to do. The crucial input is to remember Hensel's Lemma: Over each value which $P$ takes modulo $3$, there are either $3$ or $1$ values modulo $9$ assumed by $P$. So both $P$ and $P^2$ must have exactly two residues modulo $3$ which as before is absurd, since then all $P^m$ have exactly two residues modulo $3$. So $n=9$ is impossible and again we have a promising approach. Let us first generalize to $n=p^2$. As for $p=3$, we get from Hensel that above each value modulo $p$ assumed by $P$, there are either exactly one or exactly $p$ values modulo $p^2$. To find a contradiction, we should again consider the last entry in our sequence, more precisely this time the last entry where there are still $p$ residues modulo $p^2$ above one residue modulo $p$. If there are $k$ residues modulo both $p$ and $p^2$ afterwards, then before there must have been at least $k+p-1$ modulo $p^2$. Since again our sequence drops by at most a factor of $2$ in each step, we find that $k \ge p-1$. But then the number of residues modulo $p$ cannot have dropped in this step, so again it remains constant from now on, which is absurd since $p-1>1$. We are left to generalize the argument to the general case $n=p^k$. This is completely straightforward once we have the correct version of Hensel's Lemma. Indeed, we only require the following immediate consequence of Hensel: Above each value modulo $p$ assumed by $P$, there are either exactly $p^{k-1}$ or at most $p^{k-2}$ residues modulo $p^k$ assumed by $P$. The rest of the argument is now as before: We consider the last step where we are in the $p^{k-1}$-case for at least one residue modulo $p$. If we are left with only one residue modulo $p$ afterwards, then we are also only left with at most $p^{k-2}$ residues modulo $p^k$ afterwards, but before we had at least $p^{k-1}$ and so we dropped by a factor of at least $p>2$, contradiction. Similarly, if we are left with $t>1$ residues modulo $p$ afterwards, then we are only left with at most $t \cdot p^{k-2}$ residues modulo $p^k$ afterwards, but we were losing at least $p^{k-1}-p^{k-2}+1$ (since the number modulo $p$ now also has to drop by at least one) which is more than $t \cdot p^{k-2}$ and hence a contradiction.

Although my solution looks frightening, the ideas used are pretty basic or simple or standard.

Primes and powers of two work.

CANBANKAN's solution is very instructive, thanks for sharing.

Interesting problem, although I think if you've seen classical ideas before it's much easier to approach.

Solved with Ritwin and fuzimiao2013. The answer is prime $n$ and $n=2^k$ for $k \ge 0$. Construction. Here we split into the two cases for $n$. Let $n=2^k$ for some $k \ge 0$. Consider the polynomial $P(x)=2x$. In particular, $P^m(x)=2^m x$, so it is easy to see that $P^m(1), \ldots, P^m(n)$ leave exactly $\lceil n/2^m\rceil$ distinct residues modulo $n$. Let $n=p$ for some prime $p$. We claim that in fact, we can take any function $P: \mathbb{F}_p \rightarrow \mathbb{F}_p$, and $P$ can be written as a polynomial in $\mathbb{F}_p[x]$. Note that by Lagrange interpolation, we can generate a unique polynomial of degree $p+1$. The main concern however, is the fact that the coefficients are all rational and can take non-integer values. Thankfully, none of the denominators of these fractions are divisible by $p$ (which can be checked easily), so we rewrite this generated polynomial $P$ over $\mathbb{F}_p[x]$. Now consider the [directed] arrows graph $G$ over $\mathbb{F}_p$ given by $x \rightarrow P(x)$; due to the freeness on the restriction of the edges in $G$, we can draw the edges to form an Eytzinger layout, which obeys the required restriction. Claim: $G$ is a tree. Proof. This is true by the problem condition, as it eliminates the existence of a cycle. Proof that products of prime powers do not work. Let the root of $G$ be $r$. A residue $x \in \mathbb{Z}_n$ is said to have depth $\text{td}(x)>1$ if $P^{\text{td}(x)}(x)=r$ and $P^{\text{td}(x)-1}(x) \neq r$, and $\text{td}(x)$ is minimal. Let $M$ be the maximal depth in $G$, and let the height of $x$ be $M-\text{td}(x)$. In general, $G$ has a fixed number of residues of each height by the condition. It is well-known that $$M=\lfloor \log_2(n) \rfloor.$$However, noting that $\mathbb{Z}_n \cong \bigtimes \mathbb{Z}_{p^{v_p(n)}}$, we have that the maximal depth in $G$ is also $\lfloor \log_2(q) \rfloor$, where $q$ is the largest prime power in the factorization of $n$. This is a contradiction since $2q \le n$. Proof that odd prime powers do not work. This case is exactly the reason why this is an N8 and not a C8. We require one lemma, which is a consequence of Hensel's lemma. Lemma: [housekeeping] The number of residues modulo $p^k$ above each residue $x$ of $P$ modulo $p$ is either exactly $p^{k-1}$ or at most $p^{k-2}$. The key idea is that in $G$, $i \rightarrow j$ implies $\nu_p(i) \ge \nu_p(j)$. We consider into the following two cases. The bounds that follow are computed by considering the residues in the chain at $1$ modulo $p$ and $p^k$. Suppose $k \ge 3$. By the lemma, we have \[ p^{k-1}-p^{k-2}+1 \le p^{k-2} \cdot (\text{number of residues not $1$ in the range of $P$ modulo $p$}), \]which is impossible. Suppose $k=2$. By the lemma, we have \[ p - 1 \le 1, \]contradicting the parity of $p$. Thus we are done.