Problem
Description
给定一个长为 的数列 ,定义数列 :
现要求计算 的值。
Constraints
Link
Solution
Analysis
设数列 的 OGF 为 ,那么有:
但是到这一步还是不能快速求出 。考虑通过取对数来将求和变为求积,然后就可以分治 FFT 做了。
这样我们就得到了一个可以通过分治 FFT 快速求出的形式,直接做就行了。
时间复杂度 。
Code
1 |
|
退役的边界线
给定一个长为 的数列 ,定义数列 :
现要求计算 的值。
设数列 的 OGF 为 ,那么有:
但是到这一步还是不能快速求出 。考虑通过取对数来将求和变为求积,然后就可以分治 FFT 做了。
这样我们就得到了一个可以通过分治 FFT 快速求出的形式,直接做就行了。
时间复杂度 。
1 | #include <cstdio> |