「Dwango Programming Contest V E」Cyclic GCDs

题面

分析

首先看到分成圆排列不难联想到第一类斯特林数，观察其递推式：\(\left[\begin{matrix}i\\j\end{matrix}\right]=\left[\begin{matrix}i-1\\j-1\end{matrix}\right]+(i-1)\times\left[\begin{matrix}i-1\\j\end{matrix}\right]\)

发现若我们将新建一个圆排列的系数 \(1\) 改为此圆排列的最小值即为本题所求，不难发现可以将 \(a\) 数组升序排序，于是它的系数就是 \(a_i\)，即 \(f_{i,j}=a_if_{i-1,j-1}+(i-1)f_{i-1,j}\)

于是不难写出 \(f_{n,i}\) 的生成函数即为 \(\prod\limits_{i=1}^n(a_ix+i-1)\)

先给个结论：若有多项式 \(P,Q\) 和函数 \(c(F)=\gcd\limits_{i}([x^i]F)\) 则 \(c(PQ)=c(P)c(Q)\) 于是答案即为 \(\prod\limits_{i=1}^n\gcd(a_i,i-1)\)

下面考虑证明这个结论：

不失一般性的，我们只需证明 \(c(P)=c(Q)=1\) 时 \(c(PQ)=1\)，我们采用归谬法证明，设 \(c(PQ)\) 为某质数 \(p\) 的倍数，则 \(PQ\) 的最高项为 \(p\) 的倍数，那么 \(P,Q\) 中至少有一个最高项为 \(p\) 的倍数，考虑到 \(p\) 乘任何数都是 \(p\) 的倍数，故 \(P\) 的最高位不改变 \(PQ\) 中任何一项是否整除 \(p\) 设 \(P^\prime\) 为 \(P\) 去掉最高项的多项式，于是有 \(p\mid c(P^\prime Q)\) …… 以此类推，不断规约，总能规约到 \(P,Q\) 都只剩常数项，此时 \(P,Q\) 的非常数项均为 \(p\) 的倍数，而 \(c(P)=c(Q)=1\) 故二者常数项均不整除 \(p\) ，但这与 \(PQ\) 的常数项为 \(p\) 的倍数矛盾，故得证

代码

constexpr int Mod = 998244353;
constexpr int N = 100005;

int a[N];
int n;

int main() {
  read(n);
  int ans = 1;
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
  }
  std::sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) {
    ans = ans * 1ll * std::gcd(a[i], i - 1) % Mod;
  }
  write(ans), EL;
  return 0;
}