P6276 [USACO20OPEN]Exercise P(生成函数)
题目大意
求所有大小为 n 排列的阶的积 mod P。
一个排列的阶可以认为是它每个循环长度的 LCM
数据范围
(1 le n le 100000)
解题思路
对于质数 p，我们考虑如何求出它在答案中的次数。
(sum_Asum_{i=1}i[step(A)=p^i]=sum_Asum_{i=1}[p^i|step(A)])
根据这个式子，我们转化为求阶是 (p_i) 倍数的排列个数，这个也不好求，我们容斥一下用总排列数减去阶不是 (p_i) 倍数的排列即可。设 (t = p_i)
[expleft(sum_{i=1}frac{(i-1)!}{i!}x^i-sum_{i=1}frac{(it-1)!}{(it)!}
x^{it}
ight)\
=expleft(sum_{i=1}frac{1}{i}x^i-sum_{i=1}frac{1}{it}
x^{it}
ight)\
=expleft(-ln(1-x)+frac{1}{t}ln(1-x^{t})
ight)\
=frac{(1-x^t)^{frac 1t}}{1-x}
]
答案就是 ([n!x^n]frac{(1-x^t)^{frac 1t}}{1-x})
注意到 ((1-x^t)^{frac 1t}) 只有 t 的倍数上有值，(frac{1}{1-x}) 是前缀和，设 (L = lfloor frac{n}{t} floor)，有
[[n!x^n]frac{(1-x^t)^{frac 1t}}{1-x}=[n!x^{Lt}]frac{(1-x^t)^{frac 1t}}{1-x}\
=[n!x^{Lt}]frac{(1-x^t)^{frac 1t}}{(1-x)^t}\
=[n!x^{Lt}](1-x^t)^{frac 1t-1}\
=n!{L-frac 1t choose L}\
]
已经差不多了，但这里是 (mod varphi(p))，需要进一步展开。
[n!{L-frac 1t choose L}=n!frac{(L-frac 1t)(L-frac 1t-1)cdots(1-frac 1t)}{L!}\
=frac {n!}{L!t^L}prod_{i=1}^L(it-1)\
=n^{underline{n-Lt}}prod_{i=1}^L(it-1)(it-1)^{underline{t-1}}\
]
这样就是一段一段的阶乘，我们可以使用数据结构维护了。