第一行输入三个整数
代表数组中的元素数量、修改公式中的定值、操作次数。
第二行输入
个整数
代表数组元素。
在一行上输出一个整数,代表
次操作完成后数组元素和的期望。
可以证明答案可以表示为一个不可约分数
,为了避免精度问题,请直接输出整数
作为答案,其中
,
是满足
的整数。
2 6 1 3 5
11
全过程模拟如下:
![]()
的概率第一个元素硬币为正、第二个元素硬币也为正,答案为
;
![]()
的概率第一个元素硬币为正、第二个元素硬币为反,答案为
;
![]()
的概率第一个元素硬币为反、第二个元素硬币为正,答案为
;
![]()
的概率第一个元素硬币为反、第二个元素硬币也为反,答案为
;
综上,期望为
。
3 1 4 1 1 1
312500008
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)); } }