CCA的期望【牛客练习赛74】【数学】

很明显的，我们可以去算每个点变色的概率就是用单位1减去不变色的概率，那么就是这个点变色的概率了，期望就是将这些概率相加就可以了，当然，黑色点本身就是黑色的。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <string>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <limits>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <set>
12 #include <map>
13 #include <bitset>
14 #include <unordered_map>
15 #include <unordered_set>
16 #define lowbit(x) ( x&(-x) )
17 #define pi 3.141592653589793
18 #define e 2.718281828459045
19 #define INF 0x3f3f3f3f
20 #define LNF 0x3f3f3f3f3f3f3f3f
21 #define HalF (l + r)>>1
22 #define lsn rt<<1
23 #define rsn rt<<1|1
24 #define Lson lsn, l, mid
25 #define Rson rsn, mid+1, r
26 #define QL Lson, ql, qr
27 #define QR Rson, ql, qr
28 #define myself rt, l, r
29 #define pii pair<int, int>
30 #define MP(a, b) make_pair(a, b)
31 using namespace std;
32 typedef unsigned long long ull;
33 typedef unsigned int uit;
34 typedef long long ll;
35 const int maxN = 505;
36 const ll mod = 1023694381;
37 ll qpow(ll a, ll b = mod - 2)
38 {
39     ll ans = 1;
40     while(b)
41     {
42         if(b & 1) ans = ans * a % mod;
43         b >>= 1;
44         a = a * a % mod;
45     }
46     return ans;
47 }
48 int N, M, K;
49 int op[maxN];
50 ll dp[maxN][maxN], cnt[maxN] = {0}, p[maxN];
51 int main()
52 {
53 //    for(int i = 2; i * i <= mod; i ++) if(mod % i == 0) printf("%d
", i);    //prime
54     scanf("%d%d%d", &N, &M, &K);
55     for(int i = 1; i <= N; i ++) scanf("%d", &op[i]);
56     for(int i = 1; i <= N; i ++) for(int j = 1; j <= N; j ++) dp[i][j] = LNF;
57     for(int i = 1; i <= N; i ++) dp[i][i] = 0;
58     for(int i = 1, u, v; i <= M; i ++)
59     {
60         ll w; scanf("%d%d%lld", &u, &v, &w);
61         dp[u][v] = min(dp[u][v], w);
62         dp[v][u] = min(dp[v][u], w);
63     }
64     for(int i = 1; i <= N; i ++) for(int j = 1; j <= N; j ++) for(int k = 1; k <= N; k ++)
65     { dp[j][k] = min(dp[j][k], dp[j][i] + dp[i][k]); }
66     for(int i = 1; i <= N; i ++)
67     {
68         for(int j = 1; j <= N; j ++)
69         {
70             for(int k = j + 1; k <= N; k ++)
71             {
72                 if(dp[j][k] == dp[j][i] + dp[i][k])
73                 {
74                     cnt[i] ++;
75                 }
76             }
77         }
78     }
79     ll All = N * (N - 1) / 2LL;
80     All %= mod;
81     for(int i = 1; i <= N; i ++)
82     {
83         p[i] = (1 - cnt[i] * qpow(All) % mod + mod) % mod;
84         p[i] = qpow(p[i], K);
85         p[i] = (1 - p[i] + mod) % mod;
86     }
87     ll ans = 0;
88     for(int i = 1; i <= N; i ++)
89     {
90         if(op[i]) ans = (ans + 1) % mod;
91         else ans = (ans + p[i]) % mod;
92     }
93     printf("%lld
", ans);
94     return 0;
95 }