AtCoder Dwango Programming Contest V E

题目描述：

给定一个大小为\(N\)的数组\(A\),记\(f(p)\)为排列\(p\)的所有环的中的最小值的乘积。记\(b_i\)为所有形成了\(i\)个环的排列的\(f(p)\)的和。求\(b_1, b_2, ..., b_N\)的\(GCD\)模\(998244353\).

解题报告：

先将数组排序，然后想到一个和第一类斯特林数DP很类似的一个DP：

\[DP[i][j] = DP[i - 1][j - 1] * a_i + DP[i - 1][j] * i
\]

答案即为\(GCD_{i=1}^N DP[N][i]\)

记多项式\(P_i(t)\)为\(\sum_{j=1}^i DP[i][j] \cdot t^j\)

DP方程可以改写成以下形式：

\(P_i(t) = P_{i-1}(t) * (a_i * t + i)\)

\(P_N(t) = \prod_{i=1}^N (a_i * t + i)\)

引理：

	记c(P)为多项式P所有系数的GCD。有c(PQ)=c(P)c(Q)。

根据以上引理，有：\(c(P_N(t)) = \prod_{i=1}^N \gcd(a_i, i)\)

巴特西