IzumiSagiri

KazamaRuri · 2025-03-04 10:25:56 · 题解

第一类斯特林数

第一类斯特林数 n \brack m 被定义为将 n 个元素划分成 m 个互不区分的非空轮换的方案数。

其递推式为 {n \brack m} = {n-1 \brack m-1} + (n-1){n-1 \brack m} 。组合意义是考虑元素 n 所在的轮换。

分析

在本题中显然 a_i 的顺序不影响答案，考虑将其升序排序。

设 f_{n,k} 是前 n 个元素划分成 k 个置换的权值，权值是每个置换最小值的乘积。答案即为 \gcd_{k=1}^{n} f_{n,k}。

类似第一类斯特林数的递推式，我们有 f_{n,k}=a_if_{n-1,k-1}+(n-1)f_{n-1,k}。

命生成函数 F_i(x)=\sum f_{i,n}x^n，得到 F_n=F_{n-1}(a_nx+n-1)=\prod_i (a_ix+i-1)。

答案可以表示为 F_n 的各项系数的 \gcd。

Gauss's Lemma

本原多项式：各项系数 \gcd 为 1 的多项式。

高斯引理：本原多项式之积一定是本原多项式。

证明：假设有本原多项式 f,g，且对于 h=f \cdot g 的各项系数存在公共质因数 p。

找到 f(x)=\sum a_nx^n 最小的 i 使得 p \nmid a_i。

找到 g(x)=\sum b_nx^n 最小的 j 使得 p \nmid b_j。

根据本原多项式的定义可知一定存在这样的 i,j。

由于 i,j 是最小的，那么 [x^{i+j}]h(x) \equiv a_ib_j\ (\bmod\ p) 。

这说明 h 存在系数不为 p 的倍数，矛盾。

Gauss's Lemma 推广得到多项式之积的各项系数的 \gcd 等于各因式系数的 \gcd 之积。证明是 ez 的，考虑把非本原多项式的 \gcd 提出即可。

将推论套用回原题 {\rm ans}=\prod \gcd(a_i,i-1)。

时间复杂度 O(n\log n)。