824 . 好多路徑

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-dp

Description

JOI 君最喜歡圖了，他生日的時候收到了一張一般有向圖，覺得實在很一般，所以就想要在上面數有趣的東西。
他很想知道這張圖上有多少條簡單路徑。
一條簡單路徑就是從一個點經過一些邊走到另外一個點（可以完全不經過邊），過程經過的所有點（包含起終點）全部都不重複。
請你幫幫 JOI 君。

注意到因為方案數可能太大了，所以 JOI 君只在意方案數取 $10^ 9 + 7$ 的餘數。
也就是說，如果方案數為 $T$，請輸出 $T \pmod{10^ 9 + 7}$。

Input Format

輸入第一行有一個正整數 $N(N \le 20)$ 代表這張圖有幾個節點。
接下來 $N$ 行，每行都有 $N$ 個整數由一個空白隔開，第 $i$ 行第 $j$ 個數字代表 $A_{i,j}$。其中 $A_{i,j} \in \lbrace 0, 1 \rbrace$。
如果第 $i$ 個節點往第 $j$ 個節點有一題邊，則 $A_{i,j} = 1$。
否則 $A_{i,j} = 0$。

Output Format

輸出一行一個整數代表答案。

Sample Input 1

2
0 1
1 0

Sample Output 1

4

Sample Input 2

2
0 0
0 0

Sample Output 2

2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
Submit
Back to Top