保存帖子
发现
索引
热门
陶片放逐
关于
不懂就问
板块
P4238 【模板】多项式乘法逆
楼主
JK_LOVER
当前回复
11
已保存回复
11
发布时间
2020/9/18 11:28
上次更新
2023/11/5 13:03:49
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
不懂就问
JK_LOVER
楼主
2020/9/18 11:28
为什么递归时是
m
o
d
x
⌈
n
2
⌉
\bmod x^{\lceil\frac{n}{2}\rceil}
mod
x
⌈
2
n
⌉
。而不是
m
o
d
\bmod
mod
其它的什么？
时间复杂度为
T
(
n
)
=
T
(
n
2
)
+
O
(
n
log
n
)
=
O
(
n
log
n
)
T(n) = T(\frac{n}{2}) + O(n\log n) = O(n \log n)
T
(
n
)
=
T
(
2
n
)
+
O
(
n
lo
g
n
)
=
O
(
n
lo
g
n
)
。这是为什么？
2020/9/18 11:28
加载中...
