~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~
2019寒假集训题
G.Games on DAG
题面
There is a directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $M$. Edge $i$ is directed from $x_i$ to $y_i$ holds. Alse, there are no multiple edges in $G$.
Consider selecting a subset of the set of the $M$ edges in $G$, and removing these edges from $G$ to obtain another graph $G’$. There are $2^M$ different possible graphs as $G’$.
Alice and Bob play against each other in the following game played on $G’$. First, place two pieces on vertices $1$ and $2$, one on each. Then, starting from Alice, Alice and Bob alternately perform the following operation:
- Select an edge $i$ such that there is a piece placed on vertex $x_i$, and move the piece to vertex $y_i$(if there are two pieces on vertex $x_i$, only move one). The two pieces are allowed to be placed on the same vertex.
The player loses when he(or she) becomes unable to perform the operation. We assume that both players play optimally.
Among the $2^M$ different possible graphs as $G’$, how many lead to Alice’s victory? Find the count modulo $10^9+7$.