Since the graph is circularly symmetric, once you find one column of $A^{-1}$, the rest are obtained by simple rotation. It's actually very easy to formulate this as a graph labelling problem: single out one vertex $v$, and try to label each vertex of $C_n$ with a real number so that $v$'s two neighbours sum to $1$ and the neighbours of every other vertex sum to $0$.
If you think about it, such a labelling corresponds to exactly the column of $A^{-1}$ that corresponds to $v$.
You'll find that when $n$ is divisible by $4$ you end up with a contradiction, but in every other case there is a pattern that works depending on whether $n$ is $1$, $2$ or $3$ mod $4$. (Hint: satisfy the first requirement by labelling both of $v$'s neighbours with $\tfrac12$.)