给一个集合，大小为n ， 求所有子集的gcd 的期望和 。
期望的定义为 这个子集的最大公约数的K次方 ；
每个元素被选中的概率是等可能的
即概率 p = (发生的事件数)/(总的事件数);
总的事件数 = 2^n -1; 大小为n的集合的非空子集个数为2^n -1
期望 = p(i) *i;
= 1*p(1) 2*p(2) ... n*p(n);
设x发生的事件数为 dp[x] ， 则上式可化简为：
=1*dp[1]/(2^n-1) 2*dp[2]/(2^n-1) ... n*dp[n]/(2^n-1);
=1/(2^n-1)*(1*dp[1] 2*dp[2] ... n*dp[n]);
题目要求最后所得结果乘以 (2^n-1);
所以式子最后化简为：1*dp[1] 2*dp[2] ... n*dp[n]
即问题转化为求gcd = i 的子集数
假设gcd = m*i (m = 0,1,2,3,... && m*i <= max_num)的个数为dp[i]个
那么gcd = i 的个数则为 for(int j= i i ; j <= max_num ; j = i) dp[i]-=dp[j] ;
则期望为：dp[1] * 1^k dp[2] * 2^k ... dp[i] * i^k ;
代码语言：javascript复制 1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4 #include <cmath>
5 #include <iostream>
6 #include <map>
7 #include <list>
8 #include <queue>
9 #include <stack>
10 #include <string>
11 #include <algorithm>
12 #include <iterator>
13 using namespace std;
14 #define MAXN 1000010
15 #define INF 0x3f3f3f3f
16 #define MOD 998244353
17 #define eps 1e-6
18 #define LL long long
19 int num[MAXN];
20 LL dp[MAXN];
21 //dp[i] = 2^x -1 ; gcd = n*i;
22 //for(int j = i ; j <= max_num ; j = i) dp[i] -= dp[j];
23 LL qpow(LL x , LL k)
24 {
25 LL res=1;
26 while(k)
27 {
28 if(k & 1) res = res * x % MOD;
29 x = x * x % MOD;
30 k >>= 1;
31 }
32 return res;
33 }
34
35 int main()
36 {
37 int T;
38 int n,k;
39 LL ans;
40 scanf("%d",&T);
41 while(T--)
42 {
43 scanf("%d %d",&n,&k);
44 int x;
45 int max_num = 0;
46 int cunt = 0;
47 memset(num , 0 , sizeof(num));
48 memset(dp , 0 , sizeof(dp));
49 for(int i = 0 ; i < n ; i )
50 {
51 scanf("%d",&x);
52 num[x] ;
53 max_num = max(x , max_num);
54 }
55
56 ans = 0;
57 for(int i = max_num ; i >= 1 ; i --)
58 {
59 cunt = 0;
60 dp[i] = 0;
61 for(int j = i ; j <= max_num ; j = i)
62 {
63 cunt = num[j];
64 if(j > i) dp[i] = (dp[i] - dp[j] MOD) % MOD;
65 }
66 dp[i] = (dp[i] qpow(2 , cunt) - 1 MOD) % MOD;
67 ans = (ans (dp[i] * qpow(i , k)) % MOD ) % MOD;
68 }
69 printf("%dn",(int)ans);
70 }
71 return 0;
72 }
