Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add 多项式复合 O(nlog^2n) 的方法 #5492

Open
CSPNOIP opened this issue Apr 4, 2024 · 4 comments
Open

Add 多项式复合 O(nlog^2n) 的方法 #5492

CSPNOIP opened this issue Apr 4, 2024 · 4 comments
Labels
Content Request / 内容请求 New feature or request

Comments

@CSPNOIP
Copy link
Contributor

CSPNOIP commented Apr 4, 2024

页面英文名

polynomial-composition

我希望能添加的内容是

O(nlog^2n) 时间内计算多项式复合(逆)的算法,提出快三个周了

我了解到的相关参考资料有

noshi91 的原文
Aleph1022 的翻译
cyffff 的多项式复合逆题解cyfff 的多项式复合题解
此算法依赖于的转置原理
比较详细的解释与一份完整但是常数大的要死的代码

@CSPNOIP CSPNOIP added the Content Request / 内容请求 New feature or request label Apr 4, 2024
Copy link

welcome bot commented Apr 4, 2024

感谢你对 OI Wiki 的关注!记得在 Issue 中表达清楚自己的意思哦~

@r-value
Copy link
Contributor

r-value commented Apr 4, 2024

方针: OI Wiki 不是新闻的收集处
方针: OI Wiki 不是发表原创研究的场所

@HeRaNO
Copy link
Collaborator

HeRaNO commented Apr 4, 2024

这个算法与原文中提到的 SOSA '21 论文有关,也就是所谓「Bostan-Mori 算法」,这个算法的应用还有待观察和沉淀。

上面所提到的博客无法作为资料,希望进一步整理和这个算法有关的背景和前置知识。可以作为一个长期议题来添加。

@Great-designer
Copy link
Contributor

这个算法的应用还有待观察和沉淀。

希望进一步整理和这个算法有关的背景和前置知识。

因为“这个算法的应用还有待观察和沉淀”,所以不添加此算法。

但是可以研究一下“该算法的背景和前置知识”是哪些:如果“背景和前置知识”较为简单,相关内容可以添加一下;如果较为复杂,则不添加。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Content Request / 内容请求 New feature or request
Projects
None yet
Development

No branches or pull requests

4 participants