题解 P6016 【[CSGRound3]出游】
xht
2020-01-29 14:43:54
套路题。
给定一张 $n$ 个点的有向图，一开始选择一些点，这些点每次走一步，问 $T$ 步后这些点可能在哪些位置。
类似这样的问题都可以用 bitset 优化矩阵乘法做到 $\mathcal O(\frac{n^3\log T}w)$，比如 [CF576D Flights for Regular Customers](https://www.luogu.com.cn/problem/CF576D)。
~~我这题代码就是从那题的代码改的。~~
最终你会得到一个矩阵 $a$，$a_{i,j}$ 表示一开始如果 $i$ 被选择了，那么最终 $j$ 会被选。
那么 $j$ 最后不参加的概率就是所有 $a_{i,j} = 1$ 的 $i$ 一开始不参加的概率。
人数的期望就是所有人参加的概率之和。
```cpp
const int N = 500;
int n, m;
modint p[N], ans;
#define bt bitset<N>
struct mt {
bt a[N];
inline friend mt operator * (mt x, mt y) {
mt z;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (x.a[i][j]) z.a[i] |= y.a[j];
return z;
}
} a, b;
inline void ksm(mt x, int y, mt &z) {
while (y) {
if (y & 1) z = z * x;
x = x * x, y >>= 1;
}
}
int main() {
rd(n), rd(m);
for (int i = 0, k; i < n; i++) {
rd(p[i]), rd(k);
for (int j = 0, x; j < k; j++)
rd(x), a.a[--x][i] = 1;
b.a[i][i] = 1;
}
ksm(a, m, b);
for (int i = 0; i < n; i++) {
modint o = 1;
for (int j = 0; j < n; j++)
if (b.a[j][i]) o *= 1 - p[j];
ans += 1 - o;
}
print(ans);
return 0;
}
```