题目大意
一幅有向图有 $n$ 个结点，初始没有边。
有 $q$ 个操作，四种类型：
- $+\ o\ v\ k\ a_1\ \cdots\ a_k$：加入边 $(v,a_1),\cdots,(v,a_k)$
- $+\ i\ v\ k\ a_1\ \cdots\ a_k$：加入边 $(a_1,v),\cdots,(a_k,v)$
- $-\ o\ v\ k\ a_1\ \cdots\ a_k$：删除边 $(v,a_1),\cdots,(v,a_k)$
- $-\ i\ v\ k\ a_1\ \cdots\ a_k$：删除边 $(a_1,v),\cdots,(a_k,v)$
加边之前会保证原来没有这条边，删边之前会保证原来有这条边。
每次操作后，可以得到一个连通性矩阵 $a$（$a_{i,j}=1$ 表示 $i$ 能到 $j$），输出
$1 \leq n \leq 400,\ 1 \leq q \leq 800,\ 1 \leq A,B \leq 10^9$
3s
解法1
每个点维护一个 bitset 表示它能到哪些点。
每次操作时，暴力重构 $v$ 的 bitset，然后 bfs 一下把能到 $v$ 的点找出来，按拓扑序更新它们的 bitset。维护 bitset 时顺便维护答案。
对于加边操作的更新，是 $bitset_i = bitset_i \vee bitset_v$。这个的时间主要在于图的遍历，边表是 $O(n^2)$ 的，因此时间是 $O\big(q(n^2+n\frac n{64})\big)=O(qn^2)$。
对于删边操作的更新，是 $bitset_i = \bigvee_{x \in \text{out}(i)}bitset_x$（$\text{out}(i)$ 表示 $i$ 的出点），由于之前是或操作不可撤销，因此这个要对于 $i$ 枚举它的出点重新算，因此是 $O\big(q(n^2+n^2\frac n{64})\big)=O(\frac{qn^3}{64})$。
因此总的时间是 $O(\frac{qn^3}{64})$，算出来 8 亿但是跑过去了。
解法2
上面的解法，加边很优秀，但是删边不太行，这是因为删边的时候由于维护的是“是否连通”，所以无法快速撤销一个出点的影响。
那什么可以撤销呢？方案数就可以撤销！
记 $f_{i,j}$ 表示 $i$ 走到 $j$ 的方案数，给它模个 $10^9+7$ 啥的（不放心就多模几个）。
每次操作时，暴力重算 $f_{v,\cdot}$ 或者 $f_{\cdot,v}$，然后对于所有 $(i,j)$，先 $f_{i,j}-=$原来的$f_{i,v}+f_{v,j}$，再 $+=$新的$f_{i,v}+f_{v,j}$。
这样就是 $O(qn^2)$ 的了。
代码
// 解法1
1 |
|