首页 > 试题广场 >

变化的数组

[编程题]变化的数组
  • 热度指数:1061 时间限制: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上的相关章节 。

输入描述:
\hspace{15pt}第一行输入三个整数 n,m,k \left( 1\leqq n \leqq 10^5;\ 1 \leqq m, k \leqq 10^9 \right) 代表数组中的元素数量、修改公式中的定值、操作次数。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( 0 \leqq a_i \leqq 10^9 \right) 代表数组元素。


输出描述:
\hspace{15pt}在一行上输出一个整数,代表 k 次操作完成后数组元素和的期望

\hspace{15pt}可以证明答案可以表示为一个不可约分数 \frac{p}{q} ,为了避免精度问题,请直接输出整数 \left(p \cdot q^{-1} \bmod M\right) 作为答案,其中 M = (10^9 + 7)q^{-1} 是满足 q\times q^{-1} \equiv 1 \pmod{M} 的整数。
示例1

输入

2 6 1
3 5

输出

11

说明

\hspace{15pt}全过程模拟如下:
\hspace{22.5pt}\bullet\ \frac{1}{4} 的概率第一个元素硬币为正、第二个元素硬币也为正,答案为 \frac{1}{4} \times \big(3 + (3 \operatorname{and} m) + 5 + (5 \operatorname{and} m) \big) =\frac{14}{4}
\hspace{22.5pt}\bullet\ \frac{1}{4} 的概率第一个元素硬币为正、第二个元素硬币为反,答案为 \frac{1}{4} \times \big(3 + (3 \operatorname{and} m) + 5 \big) =\frac{10}{4}
\hspace{22.5pt}\bullet\ \frac{1}{4} 的概率第一个元素硬币为反、第二个元素硬币为正,答案为 \frac{1}{4} \times \big(3 + 5 + (5 \operatorname{and} m) \big) =3
\hspace{22.5pt}\bullet\ \frac{1}{4} 的概率第一个元素硬币为反、第二个元素硬币也为反,答案为 \frac{1}{4} \times \big(3 + 5\big) =2
\hspace{15pt}综上,期望为 11
示例2

输入

3 1 4
1 1 1

输出

312500008
为什么测试输入二的结果是这个数,而不是93/16?
发表于 2025-07-12 20:31:14 回复(0)
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int MOD = (int) 1e9 + 7;
    static final long[] p = new long[32];


    static long fast_pow_mod(long a, long b, long p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) != 0)
                res = (long) res * a % p;
            a = (long) a * a % p;
            b >>= 1;
        }
        return res;
    }

    public static long C(int a, int b) {
        if (a < b)
            return 0;
        long res = 1;
        for (long i = 1, j = a; i <= b; j--, i++) {
            res = (long) res * j % MOD;
            res = (long) res * fast_pow_mod(i, MOD - 2, MOD) % MOD;
        }
        return res;
    }

    public static long solve(int[] list, int n, int m, int k) {
        for (int i = 0; i < 31; i++) {
            p[i] = C(k, i) * fast_pow_mod(fast_pow_mod(2, k, MOD), MOD - 2, MOD) % MOD;
            p[31] = (p[31] + MOD - p[i]) % MOD;
        }
        p[31] = (1 + p[31]) % MOD;

        long res = 0, x;
        for (int i = 0; i < n; i++) {
            x = list[i];
            for (int j = 0; j < 32; j++) {
                res += x * p[j] % MOD;
                res %= MOD;
                x += x & m;
            }
        };
        return res;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = in.nextInt();
        }

        System.out.println(solve(list, n, m, k));
    }
}

发表于 2025-06-28 01:51:50 回复(0)