The characteristic polynomial of such special matrix? 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.
