D套个多项式指数和多项式乘法的板子就可以做到n = 1e5 了...