P5216 DLS 采花

    • 107通过
    • 489提交
  • 题目提供者 SXnoname
  • 评测方式 云端评测
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    超水的签到题

    题目描述

    DLS 有 $N$ 个花田,每个花田里有 $a_i$ 朵花。

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

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

    输入输出格式

    输入格式:

    第一行一个正整数 $N$。
    第二行是一个长度为 $N$ 的序列 $a$。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4
    2 3 6 3
    
    输出样例#1: 复制
    156

    说明

    数据百分比 限制
    $50\%$ $N \le 9$
    $80\%$ $N \le 1000$
    $100\%$ $N \le 10^5,a_i \le 10^5$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。