题意：给出自然数序列 ，对每个 ，分别求满足下列条件的 的方案数：
答案对 取模，。
构造多项式 。特殊地，规定
，
为十进制不进位加法，多项式乘法对应数列的十进制不进位加法卷积。根据组合意义， 的各项系数即为答案。
，只需先计算
，将点值 次方，再计算 即可。
这听起来很容易实现，其实有两个大问题：
- 模 下没有 的逆元，而计算 时要除 。
- 记 ，模 下没有本原单位根 ，无法构造位矩阵。
第一个问题不难解决，注意到
有逆元，扩到 下计算，最后将
直接除掉即可。
对于第二个问题，考虑扩域，定义代数对象 满足 ，一个简单的想法是循环卷积，即在
下计算。
满足单位根 所需的所有性质吗？我们有 互不相同，，似乎符合要求。但细想能发现漏洞：模
下的多项式根本不是群，即是说，有些元素没有乘法逆，例如 ，由于是 的因式，它没有乘法逆。这会破坏“FFT
计算的是循环卷积”的证明，让我们的算法失效。
接下来要找到一种合适的扩域方法，避免不能除的问题。
- 引理
证明：每个
次单位根必定是某个
次本原单位根（其中 ），且只被计入一次。
由上述引理可得到
的计算方法。首先取对数： 施莫比乌斯反演，再取指数：
- 分圆多项式的性质
- 分圆多项式必为整系数多项式。
- 分圆多项式在
上不可约。
证明略。
证明：首先显然有 ，则 假设对于 有 ，则 。
考虑 次本原单位根 。根据定义 ，但是
显然没有 这个根，，矛盾。
分圆多项式在
上不可约，这保证了
下每个多项式都有乘法逆元。虽然我们在模意义下计算，不必考虑
在模意义下是否可约，因为我们可以视为在 上计算，最后取模。
经过如上准备，我们发现 符合 次本原单位根所需的所有性质。本题中
，。
PT/IPT 和快速幂需要计算 次乘法，若对
暴力计算多项式乘法与取模，复杂度 。
为了简化计算，由引理注意到 ，可以先在 下计算，最后再对
取模。这样就变成了简单的循环卷积。PT/IPT 变换中需要乘单位根 ，在 下只有一项 ，可以 乘上。复杂度优化为 。