F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

败北

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
3 3 2 5 2 3 2 3 2 101 6 001 9 101 5 001 7 001 5 1 5 3 2 2 00110 6 00111 2 10100 2 11001 3 01101 5 8 5 2 1 2 5 2 5 2 4 3 4 4 1 3 5 3 2 10 00101 4 01111 10 00001 3 01110 1 10100
 

Sample Output
4 6 81 5 7 4 216 4 8 9 45 6 10 1 1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 17:48:25, Gzip enabled