打卡信奥刷题（2899）用C++实现信奥题 P5216 DLS 采花

P5216 DLS 采花

题目背景

超水的签到题

题目描述

DLS 有NNN个花田，每个花田里有aia_iai​朵花。

DLS 喜欢稀奇古怪的花田，他希望重新排列花田，然后去采花。
但 DLS 采花又有一个癖好：他会从左往右采花。
若当前采到第iii个花田，在之前有一个花田的花的数量，是第iii个花田的花的数量的因子的话，那么 DLS 不会采这个花田的花。

现在，DLS 想知道对于所有排列花田的方案，他能够采到的花的数量的和是多少。
由于答案会比较大，请对998244353998244353998244353取模。

输入格式

第一行一个正整数NNN。
第二行是一个长度为NNN的序列aaa。

输出格式

共一行，表示所有方案中采花的数量和对998244353998244353998244353取模的结果。

输入输出样例 #1

输入 #1

4 2 3 6 3

输出 #1

156

说明/提示

C++实现

#include<cstdio>constintMAXN=1e5+5,MOD=998244353;intn;intf1[MAXN],f2[MAXN];intcnta[MAXN],cntb[MAXN];intans;intmain(){scanf("%d",&n);f1[0]=1;for(inti=1;i<=n;i++)f1[i]=1ll*f1[i-1]*i%MOD;f2[n+1]=1;for(inti=n;i>0;i--)f2[i]=1ll*f2[i+1]*i%MOD;for(inti=1;i<=n;i++){inta;scanf("%d",&a);cnta[a]++;}for(inti=1;i<=1e5;i++)if(cnta[i]){for(intj=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);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容