首页 > 试题广场 >

小红的点赞

[编程题]小红的点赞
  • 热度指数:285 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小红在整理自己小红书上发布的笔记时,会发现,每过一段时间,都会随机有一个笔记点赞数量加 1(每个笔记被点赞的概率是相同的)。
现在小红想知道,当第一次出现所有笔记点赞数量均为偶数时,所有笔记的总赞数之和的期望是多少?

输入描述:
第一行输入一个正整数n,代表小红发布的笔记数量。
第二行输入n个非负整数a_i,代表当且每个笔记的点赞数量。
1\leq n \leq 10^5
0\leq a_i \leq 10^9


输出描述:
一个整数,代表最终总赞数的期望对10^9+7取模的值。可以证明,最终的答案一定是个有理数,你只需要输出其对10^9+7取模的结果。
分数取模的定义:假设答案是x/y,那么其对p取模的答案是找到一个整数a满足a∈[0,p-1]a*yp取模等于x
示例1

输入

2
1 2

输出

6

说明

1/2的概率总赞数为 4,1/4概率总赞数为 6,1/8概率总赞数为 8……以此类推,最终的期望为1/2*4+1/4*6+……,这个无穷级数收敛于 6。
头像 美丽的布莱恩想要offer
发表于 2025-06-22 08:18:11
MOD = 1000000007 # 扩展欧几里得算法 def extended_gcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = extended_gcd(b % a, a) 展开全文
头像 杜宜宸
发表于 2025-09-18 00:54:28
小红的点赞题解 显然,这道题具体的数是多少并不重要 我们只关心奇数与偶数的个数 设为奇数个数为时的还原为偶数的期望 我们有 对于 或 有与 此处不依赖数学直觉,将其转换为 使得而是选择高斯消元 对于每一个表达式 有 可列出行列式 1 0 0 ... ... ... ... 0 1 展开全文
头像 丨阿伟丨
发表于 2025-09-15 16:03:51
REAL689 小红的点赞 题目链接 小红的点赞 题目描述 小红有 篇笔记,初始点赞数分别为 。在每个时间单位,都会有一篇随机的笔记( 篇中的任意一篇,概率均等)点赞数加 1。 问:当第一次出现所有笔记的点赞数均为偶数时,所有笔记的总点赞数之和的期望是多少? 答案需要对 取模。 解题思路 这是一 展开全文