很多两年前学过的东西已经忘了, 虽然很大一部分原因在于当时就没有学明白, 但还是有一种原有的认知落空的感觉.

综述

在 OI/XCPC 中, FFT 常用于加速卷积的计算. 此外, 配合牛顿迭代得到的一系列多项式算法提供了对生成函数进行快速运算的方法, 因此在许多计数问题中也 FFT 也很有用.

阅读全文

题目链接

• https://loj.ac/problem/2541

这是一道经常被拿出来四处安利的题 (

阅读全文

• 题目链接: https://uoj.ac/problem/449

个人现在感觉这是一道有启发意义的期望题.

大体是利用 Min-Max 容斥计算期望, 以及 NTT 优化时间复杂度.

阅读全文

• 题目链接: https://uoj.ac/problem/335

大概是利用树的 Prufer 序列解决某些计数问题, 第一次见感觉很新鲜.

阅读全文

• 题目链接: https://www.luogu.com.cn/problem/P4191

这道题真是奥妙重重, 直接暴露了我 FFT 那一套单位根的东西没搞懂 = =

阅读全文

综述

看到洛谷上有求 Stirling 数的神奇板子, 于是就想写 = =

虽然不知道会有什么用处, 其实是不想写题又不敢颓废吧

大概是一些式子推推推然后拉板子算算算…

阅读全文

题目链接

• https://www.51nod.com/Challenge/Problem.html#problemId=1348

分治 FFT 如果使用三模数 NTT, 那么每次合并只需要记录实际模数下的答案…

阅读全文

组合数学学不明白祭.

• 题目链接: https://lydsy.com/JudgeOnline/problem.php?id=5093

根据题意列出式子, 并通过第二类 Stirling 数对式子进行化简, 在合适的时间内计算出结果.

阅读全文

我不如小学生.png

作为高中生, 被小学奥 (chang) 数 (shi) 针对了.

于是, 这里集中了形如 $\sum_{i=1}^n i^a, (a = 1, 2, 3, \ldots )$, 即前 $n$ 个正整数的 $a$ 次方和的计算公式.

阅读全文