传送门 很好的一道生成函数+NTT题，做完之后可以加深对生成函数的理解。 建议先弄懂卡特兰数是怎么用生成函数推的，参考这篇博客（只用看推到C(x)=\frac{1\pm\sqrt{\dfrac}{2}的部分） 考虑我们是怎么推导出nnn节点二叉树的种类数为卡特兰数的，考虑根节点两边连出的子树，他们的方案数为cn−i−1×cic_{n-i-1} \times c_{i}cn−i−1​×ci​。...

NTT 有时候，题目要求对一个大质数（特别是998244353之类的数）取模，就不能用FFT，而是用NTT。 NTT采用原根替代单位根，如果不了解原根，请参考这篇博客。 常见NTT质数表： a×2b+1a\times 2^b+1a×2b+1 a b g 3 1 1 2 5 1 2 2 17 1 4 3 97 3 5 5 193 3 6 5 257 1 8 ...