[ATCoder] Cyclic GCDs - 神圣的数学题

YipChipqwq / 2024-11-07 / 原文

Cyclic GCDs

题面

【题目描述】

给定一个长为 $N$ 的序列 $a_1,a_2,\dots,a_N$。

设一个置换 $p$ 的价值 $f(p)$ 为每个轮换中最小的 $a_i$ 的乘积。

设 $b_i$ 为有 $i$ 个轮换的所有置换 $p$ 的 $f(p)$ 之和。

求 $\gcd(b_1,b_2,\dots,b_N) \bmod{998244353}$。

【数据范围】

$1\le N\le10^5$，$1\le a_i\le10^9$。

【样例输入】

4
2 5 2 5

【样例输出】

题解

抽象的证明，美妙的公式，好一道数学题。

首先，对整个序列划分轮换，不就是将其分为 $k$ 个不交集合吗？

其次，要求每个集合中的最小值，不就等于将序列从小到大排序后取划分左端点吗？

如此，我们考虑一个函数 $F_{i,j}$ 表示前 $i$ 个数划分为 $j$ 个集合的价值之积的和，则 $F_{n, i} = b_i = \sum f(p)$，有如下式子：

\[F_{i,j} = a_i \times F_{i-1,j-1} + (i - 1) \times F_{i-1,j} \]

如果新加入一个数，自成一个轮换，那么对 $f(p)$ 贡献一个 $a_i$ 的乘积，我们得到了 $a_i \times F_{i-1,j-1}$ 这个式子。
如果新加入一个数，插入其他轮换，那么前面 $i - 1$ 个数有 $i - 1$ 个位置可供插空，则对 $b_i$ 贡献一个所有满足条件的置换之和，我们得到了 $(i - 1) \times F_{i-1,j}$ 这个式子。

这个式子和斯特林数十分相似，我们考虑引入 $G_i(x) = \sum\limits_{j = 0}^n F_{i,j}x^i$ 这个生成函数。

明显的，我们可以使用形式幂级数代换原递推式得到：

\[[x^j]G_i(x) = [x^{j-1}]a_iG_{i-1}(x) + [x^{j}](i - 1)G_{i-1}(x) \]

根据幂形式的性质，给 $j-1$ 次项乘上 $x$ 可以得到等幂式，又可以缩回我们的生成函数，即：

\[\begin{aligned} G_i(x) &= a_ixG_{i-1}(x) + (i - 1)G_{i-1}(x)\\ &= (a_ix + i - 1)G_{i-1}(x) \end{aligned} \]

而 $G_n(x)$ 便是我们需要求得的 $n$ 元 $j$ 次划分贡献的生成函数。

于是我们有：

\[\begin{aligned} G_n(x) &= (a_nx + n - 1)G_{n-1}(x)\\ &= (a_nx + n - 1)(a_{n-1}x + n - 2)G_{n-2}(x)\\ &= (a_nx + n - 1)(a_{n-1}x + n - 2)...(a_2x - 1)a_1\\ &= \prod_{i = 1}^n (a_ix + i - 1) \end{aligned} \]

而 $b_i = [x^i]G_n(x)$，我们想求 $\gcd(b_1,b_2,...,b_n) = \gcd\limits_{i = 1}^n [x^i]G_n(x)$，很自然的联想到在 $G_n(x)$ 上下手。

设 $m = \gcd\limits_{i = 1}^n [x^i]G_n(x)$。

我们考虑将其因式分解，有 $G_n(x) = m(c_1x + d_1)(c_2x + d_2)...(c_nx + d_n)$。

对于任一 $[x^i]G_n(x)$，我们总能得到 $m \times P$，$P$ 为不能再分解的因式，因此我们得到 $\gcd(b_1,b_2,...,b_n) = m$。

而根据 $m = \prod\limits_{i=1}^n \gcd(a_i, i - 1)$，我们得出结论：

\[\gcd(b_1,b_2,...,b_n) = \prod\limits_{i=1}^n \gcd(a_i, i - 1) \]

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
int n, a[N], ans = 1;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i ++ ) ans = 1ll * ans * __gcd(a[i], i - 1) % mod;
	cout << ans;
	return 0;
}