链接
题意
给出$n$个点,每个点都有一条弧连接着一个其他的点,对于给出的弧,可以选一部分进行反转使得图中没有环,输出操作的方法数对$10^9+7$取模后的值。
思路
易得,弧的方向对结果不产生影响,将弧转为无向边考虑。显然,对于任意连通分量都至多有一个环。每个环的反转方式为$2^e-2$,不在环中的每条边的反转状态任意。最终的结果为$2^{n-\sum e} \prod {\left(2^e-2\right)}$。
代码
|
|
A little brute force is always helpful.
给出$n$个点,每个点都有一条弧连接着一个其他的点,对于给出的弧,可以选一部分进行反转使得图中没有环,输出操作的方法数对$10^9+7$取模后的值。
易得,弧的方向对结果不产生影响,将弧转为无向边考虑。显然,对于任意连通分量都至多有一个环。每个环的反转方式为$2^e-2$,不在环中的每条边的反转状态任意。最终的结果为$2^{n-\sum e} \prod {\left(2^e-2\right)}$。
|
|