from AtCoder Library Practice Contest ACLPC_F F - Convolution 素朴に畳み込みをするとO(NM) FFTで使われるバタフライ演算を応用するとO(N logM) https://www.onosokki.co.jp/HP-WK/eMM_back/emm140.pdf NTTという選択肢もあるらしい