Rt,最近在学多项式学得有点崩溃,因为代码太乱了,数组东一个西一个,所以便有了这个念头
但是本人码力不好而且不会太多C艹小特性,所以在实操的时候发现了很多细节难以实现,其中最重要的(甚至是最最基础的)问题在这里:
如何同时兼备常数与独立性(换句话说就是避免在类外声明过多辅助内存,比如在进行乘法时拷贝出去再NTT,最后再拷贝回来逆NTT,这样子全局的变量太多会很乱,总而言之还是要优雅)
我是这样想的:保证常数就要尽量地减少一些大规模的拷贝行为,但这似乎无法避免!
比如最重要的就是返回值的问题——如果每次一返回就是一个 int[1e6],那不会爆炸吗?
而换成你 STL 的动态容器(如 vector)来的话也很不方便。知周所众,你 FFT/NTT 对于容器大小有很严格的要求(必须预留足够的空间,达到 2k 的形式),所以要容器要兼备 快速扩容 & 快速清理冗余内存 的能力,这要求明显太高了(您 while(...){push_back(...)/pop_back();} 也不是个法啊对吧)
怎么办呢?挺急的求大佬