恋兔光

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

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

轮换不好做，考虑变成集合，假设有若干个集合，那么一个集合就可以贡献

(|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，然后这个题就做完了，生成函数是什么？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

附上无敌优美代码

CPP

#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;
}

文章操作

相关推荐

评论

恋兔光