题解 P5216 【DLS 采花】

题解：

考虑算每个数对答案的贡献。

第i个数的有贡献，当且仅当第i个数的约数出现在它后面。

假设第i个数有x个约数，那么有贡献的概率就是，有贡献的方案数就是总方案数概率。

为什么是呢?有个数，要选出那个数放在最前面，当然是。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
#define int long long
const int N=1e6+5;
const int mod=998244353;
int n,ans,a[N],b[N],gs[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return res;
}
signed main()
{
    n=read();
    int jc=1;
    for(int i=1;i<=n;i++)jc=jc*i%mod;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        b[a[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j*j<=a[i];j++)
            if(a[i]%j==0)
            {
                gs[i]+=b[j];
                if(j*j!=a[i])gs[i]+=b[a[i]/j];
            }
        ans=(ans+jc*kuai(gs[i],mod-2)%mod*a[i]%mod)%mod;
    }
    cout<<ans;
}