首页 > 试题广场 >

序列取反问题

[编程题]序列取反问题
  • 热度指数：53 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有 个牛牛排成一排，从头到尾编号为 到 ，牛牛们都有一个可爱值，对于牛牛 ，记它的可爱值为 ， ，特别地，我们令 。这次我们的任务是把牛牛全部变成快乐的牛牛，起初所有牛牛都不快乐，每次我们从不快乐的牛牛中等概率选择一个，设选出来的是 ，把编号 到 中的不快乐的牛牛全部变成快乐的牛牛，一次这样的操作记为1步。问让全部不快乐的牛牛都变成快乐的牛牛的期望步数。
由于牛牛们都很有特色，所以对于任意 ，均满足条件：若 ，则 ， 这两个条件一定满足其中1个。
答案对998244353取模。
设答案为 ，其中 ，输出 ，要求 为满足 的最小整数。
输入时，给出数 ， 将以数组 的形式给出，详细见样例。
示例1

输入

5,[5,4,3,4,5]

输出

665496238

说明

答案为8/3，在对998244353取模的情况下是665496238
示例2

输入

6,[6,4,3,4,6,6]

输出

3

备注:
n<=200000，i<=ai<=n

算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

数组 基础数学
难度：
0条回答 529浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号