As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:23:48
Last updated: 2025-12-13 00:23:52
考虑分治求解。
$$ (a_0,a_1,a_2)*(b_0,b_1,b_2)=(a_1b_1+a_1b_2+a_2b_1+a_2b_2,a_0b_0+a_0b_2+a_2b_0,a_0b_1+a_1b_0) $$
暴力求解需要九次乘法，但是 $$ (a_0,a_1,a_2)*(b_0,b_1,b_2)=((a_1+a_2)(b_1+b_2),(a_0+a_1+a_2)(b_0+b_1+b_2)-(a_1+a_2)(b_1+b_2)-a_0b_1-a_1b_0,a_0b_1+a_1b_0) $$ 将乘法次数减少到了四次。
时间复杂度 $T(k)=3^k+4T(k-1)=O(4^k)$。