|
||||||||||
败北Time Limit: 10000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 59 Accepted Submission(s): 20 Problem Description 给定一张 $n$ 个点 $m$ 条边的 DAG。 $q$ 组询问,每次给出集合 $S$ 和 $k$,你要求出对 $S$ 内所有点赋 $[1,k]$ 内的权值,记点 $p$ 的权值是 $a_p$,使得所有满足 $u,v \in S$ 的边 $u \to v $ 满足 $a_u > a_v$ 的方案数,答案模 $10^9+7$。 注意保证无自环但可能有重边,如果 $S$ 为空集答案为 $1$。 Input 本题有多组数据。第一行一个正整数 $T$($1\le T\le 5$),表示测试数据组数。 对于每组数据,第一行三个整数 $n,m,q$($1 \le n \le 20,0 \le m \le \dfrac{n(n-1)}{2},1 \le q \le 10^5$)。 接下来 $m$ 行每行两个整数 $u,v$ ($1 \le u,v \le n$)描述图的一条有向边 $u \to v$。 接下来 $q$ 行,每行先是一个正整数 $k$($1 \le k \le 10^9$),接下来是一个长度为 $n$ 的 $01$ 串 $s$,$s_i=1$ 代表 $i \in S$,否则 $i \notin S$。 保证图无环。 Output 对于每组数据,输出 $q$ 行,每行一个整数,表示赋权值方案数对 $10^9+7$ 取模后的结果。 Sample Input
Sample Output
Source | ||||||||||
|