how to find the characteristic polynomial of $A$, while $\forall i+j>n+1, a_{ij}=0?$
$$\begin{pmatrix} a_{11} & a_{12} &\cdots & a_{1,n-1} & a_{1,n} \\ a_{21} & a_{22} &\cdots & a_{2,n-1} & 0 \\ \vdots & \vdots &\ddots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \cdots & 0 & 0\\ a_{n,1} & 0 & \cdots & 0 & 0\end{pmatrix}$$
I know a fast algorithm that can solve the characteristic polynomial of any matrix in $O(n^3)$，but this matrix is too special that I wonder if there's a better solution?
A way of simplifying the characteristic polynomial computation of this anti-diagonal matrix is using the determinant of a block matrix.
Namely, if we have a matrix $(n+m) \times (n+m)$ matrix $X$ in block form: $$ X = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$$ where $A,D$ are square matrices of sizes $n,m$ resp. and $C,D$ are rectangular matrices, then $$\det X = \det(A -BD^{-1}C)\det(D),$$ if $D$ is invertible.
In your case, if you want to compute the determinant of $X= M-λI_n$ if $M$ is of size $n= 2k$ or $2k+1$. then the matrix $D= - λ I_k$, so the characteristic polynomial $P_k$ becomes $$ \det (M-λI_n) = (-λ)^k \det(m) $$ where $m = A- λI_{k} -\frac{1}{λ}BC$ is a $(k\times k)$ matrix.
PS. Apologies for the confusing answer before, I misread your question.