首页 > 试题广场 >

变化的数组

[编程题]变化的数组

热度指数：1071 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ 和一个整数 $m$ ，保证全部非负。你需要执行 $k$ 次操作，每一次操作如下：
$\hspace{22.5pt}\bullet\$ 对数组中的每一个元素 $a_i$ ，投掷一次硬币，若硬币为正则将这个元素修改为 $a_i + (a_i \operatorname{and} m)$ ；反之，则不操作；

$\hspace{15pt}$ 在全部 $k$ 次操作完成后，求解数组元素和的期望。

$\hspace{15pt}$ 在本题中， $\operatorname{and}$ 运算即按位与运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki上的相关章节 。

输入描述:

第一行输入三个整数  代表数组中的元素数量、修改公式中的定值、操作次数。
第二行输入  个整数  代表数组元素。

输出描述:

在一行上输出一个整数，代表  次操作完成后数组元素和的期望。

可以证明答案可以表示为一个不可约分数  ，为了避免精度问题，请直接输出整数  作为答案，其中  ， 是满足  的整数。

示例1

输入

2 6 1
3 5

输出

说明

全过程模拟如下：
  的概率第一个元素硬币为正、第二个元素硬币也为正，答案为  ；
  的概率第一个元素硬币为正、第二个元素硬币为反，答案为  ；
  的概率第一个元素硬币为反、第二个元素硬币为正，答案为  ；
  的概率第一个元素硬币为反、第二个元素硬币也为反，答案为  ；
综上，期望为  。

示例2

输入

3 1 4
1 1 1

输出

312500008

算法知识视频讲解

Bezime

发表于 2024-12-08 21:02:07

F题题解：大致思路：先看操作成功的规律：对于一个和，按二进制来看的最低位（即 lowbit）加进中，会变为，并进位，而更低位的值不会变化。下一次的最低位将会变高，而当的最低位比的最高位还高时，的值将不会发生变化。举个例子：如果（二进制表展开全文

番禺小韭菜

发表于 2025-03-04 15:58:37

#include<bits/stdc++.h> #define ll long long #define MO 1000000007ll #define MXN 1000002 using namespace std; inline void rd(ll& x) { x 展开全文

牛客856751393号

发表于 2025-03-06 17:33:36

运行时间超时了，但是不提示超时。 def ksm(a, b): # 快速幂计算 a ** b s = 1 while b: if b & 1: s = s * a % MOD a = a * a % MOD 展开全文

想玩飞盘的长颈鹿刷了100道题

发表于 2025-06-05 19:24:00

import sys def input(): return sys.stdin.readline().strip() MOD = 10**9 + 7 MAXI = 31 fac = [1] * (MAXI + 1) ifac = [1] * (MAXI + 1) for i in range( 展开全文