恋兔光

· · 题解

不要猜结论！不要生成函数！

生成函数马上就要变成十级算法了，怎么还在学这种鬼东西？

轮换不好做，考虑变成集合，假设有若干个集合，那么一个集合就可以贡献 (|S|-1)! 种方案，然后一个分组方案自然就是每个集合的方案的乘积。

也就是说，假设现在有一个大小为 |S| 的集合，你往里面塞一个数，相当于会多出来 |S| 种方案，也就是乘上集合大小。

那你设 dp_{i,j} 表示前 i 个数，有 j 个集合，那你加入一个点，可以新开一个集合，也就是乘上 A_{i+1} 转移给 dp_{i+1,j+1}，或者跟在别人后面，也就是乘上 i 再转移给 dp_{i+1,j}，然后我们就获得了一个平方的解法。

考虑把这个东西的图像画出来，容易发现最后 b_i 由一条条从 (0,0) 到 (n,i) 的路径组成。

如果要求和还要 gcd 十分不牛，如果能把 b 拆成若干条路径，就方便很多。

于是我们大胆猜想，我们一定能够使用某一条路径卡死 gcd 的其中一个因子。

首先是正确性，考虑我们枚举质因数 i，对于 i 的每个倍数 j，检查他是开一个新的集合更优，还是接在前面更优，这样就可以求出最严的路径，那正确性就显然了，我这条路径的 i 的含量是最低的，那所有的路径都含有这么多 i，那肯定就是有用的了。

然后还是正确性，考虑为什么这条路径一定能够严到，b_i 不是加和吗，有没有可能加到最后 i 还多出来一个，但是你考虑把所有有正收益的点取走之后，假设最后停在 b_k，那么一定没有任何别的 i 的次数和他一样多的同样出现在 b_k 里，原因显然，你把正贡献全取走了，零贡献如果选择其中一个就不会存进 b_k 里了。

然后我们就证明了，我们的答案一定会卡死 gcd，然后这个题就做完了，生成函数是什么？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

附上无敌优美代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int A[1000005];
const int P=998244353;
bool flg[1000005];
int getcnt(int x,int y){
   int cnt=0;
   while(x%y==0)x/=y,cnt++;
   return cnt;
}
signed main(){
   scanf("%lld",&n);
   for(int i=1;i<=n;i++){
      scanf("%lld",&A[i]);
   }
   sort(A+1,A+1+n);
   int ans=1;
   for(int d=2;d<n;d++){
      if(flg[d])continue;
      int all=0;
      for(int j=1;j*d<n;j++){
         flg[j*d]=true;
         int tmp1=getcnt(j*d,d);
         int tmp2=getcnt(A[j*d+1],d);
         all+=min(tmp1,tmp2);
      }
      while(all--)ans=ans*d%P;
      // ans=ans*power(d,all)%P;
   }
   printf("%lld\n",ans*A[1]%P);
   return 0;
}