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
【样例输出】
2
题解
抽象的证明，美妙的公式，好一道数学题。
首先，对整个序列划分轮换，不就是将其分为 \(k\) 个不交集合吗？
其次，要求每个集合中的最小值，不就等于将序列从小到大排序后取划分左端点吗？
如此，我们考虑一个函数 \(F_{i,j}\) 表示前 \(i\) 个数划分为 \(j\) 个集合的价值之积的和，则 \(F_{n, i} = b_i = \sum f(p)\)，有如下式子：
-
如果新加入一个数，自成一个轮换，那么对 \(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\) 这个生成函数。
明显的，我们可以使用形式幂级数代换原递推式得到：
根据幂形式的性质，给 \(j-1\) 次项乘上 \(x\) 可以得到等幂式，又可以缩回我们的生成函数，即：
而 \(G_n(x)\) 便是我们需要求得的 \(n\) 元 \(j\) 次划分贡献的生成函数。
于是我们有：
而 \(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)\)，我们得出结论：
#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;
}
