@[a2956331800](/space/show?uid=9517) reverse?你指的是蝴蝶操作吗QAQ 蝴蝶操作不做大概是递归版吧
by 老K @ 2019-01-03 21:52:36
有 reverse 的代码肯定没有求原根的逆元
为什么?单位复根的逆元是它的共轭,而NTT数列是共轭对称的
乘一个len的逆元是你没看懂 FFT
by 小粉兔 @ 2019-01-03 21:53:19
@[小粉兔](/space/show?uid=10703) Orz
by 老K @ 2019-01-03 21:53:58
FTT 在复数系上做卷积,NTT 只不过换到了循环群上。单位根变原根而已。
其他部分都是一样的。
by GNAQ @ 2019-01-03 21:54:10
@[小粉兔](/space/show?uid=10703) 所以reverse指的是蝴蝶操作吗
by 老K @ 2019-01-03 21:54:19
@[老K](/space/show?uid=8943) orz 您今年WC准备唱什么歌
by 小粉兔 @ 2019-01-03 21:54:32
@[GNAQ](/space/show?uid=21512) FTT是蛤子?
by Stella_Yan @ 2019-01-03 21:55:03
@[小粉兔](/space/show?uid=10703) $\cot 0$
by 老K @ 2019-01-03 21:55:04
@[老K](/space/show?uid=8943) 不是……
指的是:
```cpp
if (type == -1) {
std::reverse(A + 1, A + Len);
...
}
```
by 小粉兔 @ 2019-01-03 21:55:16
@[小粉兔](/space/show?uid=10703) 所以reverse指的是蝴蝶操作吗
by 老K @ 2019-01-03 21:55:27