题解 P5216 【DLS 采花】

· · 题解

看完求点赞，我每看一篇不管好不好都点赞的

我看没人写，自己随便写一点吧

这题其实很像小学奥数

简化题目：对于每个花田，只要求有多少种情况这个花田会被采到。

也就是说，这个花田前面不能有它的因子，求排列总数。

首先我们考虑的是，一个花田有多少个因子。

排列时，这个花田必须排在所有它的因子前面，剩下不是它的因子的数，随便排

小学奥数闪亮登场

先看看一组自己的数据

6
1 1 2 2 2 3

我们只考虑3的排列

根据小学奥数，先把3和两个1排好

3 1 1

当然，两个1的位置可以随意排列，先把方案数乘 2!

接着把剩下的三个数，三个2随意在这些空位放

第一个2，可以放在以下位置：

_ 3 _ 1 _ 1 _

方案数乘4

第二个2有5个位置可以放，方案数乘5

以此类推

注意最后会乘到 n ，我比赛的时候没发现结果还绕弯路打 st 表，不过还是过了

有人会问，要不要乘 3!

不用，因为已经是随便排的了

细节问题

求一个花田在其他花田中有多少个因子

这里不能用 O(n^2) 的暴力，必须优化

我们可以用桶排，从小到大枚举，枚举到一个数就把它的倍数用另一个桶表示

复杂度 O(10^5*(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...+\frac{1}{10^5}))

用 cnta 数组表示花田为 i 的数量（这句话看不懂可以看代码）

for(int i=1;i<=n;i++){
    int a;  //花的数量
    scanf("%d",&a);  //读入
    cnta[a]++;  //桶排
}

接着，用 cntb 数组表示这个数有多少个因子

for(int i=1;i<=1e5;i++)  //枚举桶
    if(cnta[i]){      //如果有这个数
        for(int j=i;j<=1e5;j+=i)  //枚举倍数
            cntb[j]+=cnta[i];  //这段代码看这里
    }

然后，if 语句后面有大括号，就是求解过程

注意 cntb 那里 i 也是算了的，因为可能有多个相同的数，比如样例中有两个3。这是为了数组表意更明确，因子也包括自己

已知一个数有 x 个因子，方案数为：

(x-1)! * \frac{n!}{x!}

变成 \frac{n!}{x} 这里要注意，有取模，所以我们不能把 n! 存下来再除以 x

其实刚才那个已经可以 O(1) 求解了

用一个数组表示 i!，另一个数组表示 \frac{n!}{i!}

这两个东西都是 O(n) 预处理的

于是这题就到此为止了

代码

#include<cstdio>
const int MAXN=1e5+5,MOD=998244353;
int n;
int f1[MAXN],f2[MAXN];
int cnta[MAXN],cntb[MAXN];
int ans;
int main(){
    scanf("%d",&n);
    f1[0]=1;
    for(int i=1;i<=n;i++)
        f1[i]=1ll*f1[i-1]*i%MOD;
    f2[n+1]=1;
    for(int i=n;i>0;i--)
        f2[i]=1ll*f2[i+1]*i%MOD;
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        cnta[a]++;
    }
    for(int i=1;i<=1e5;i++)
        if(cnta[i]){
            for(int j=i;j<=1e5;j+=i)
                cntb[j]+=cnta[i];
            ans=(ans+1ll*i*cnta[i]%MOD*f1[cntb[i]-1]%MOD*f2[cntb[i]+1]%MOD)%MOD;
        }
    printf("%d\n",ans);
    return 0;
}

话说这是“超水的签到题”吗，还有紫题啊，我这个初一的蒟蒻还能做出来，不可思议！

看完博客记得点赞啊，我每看一篇都点的