[HOJ 300][Codechef]Party Invitation (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/300_files/extensions/MathMenu.js

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 300 - Party Invitation

Problem Statistics

Solved Member: 5　　Submission: 12　　User Tried: 5

Problem：

瀚瀚有 n 位碰友，分別以 1,2,3,...,n 來編號。他今天想要邀請一些人來家裡一起7122。

然而，對於每一個碰友 i，會有一個特定討厭的碰友 a_i，代表瀚瀚不能同時邀請 i 與 a_i 兩個人，否則他們會打架，瀚瀚就7122不出來了。

請你找出瀚瀚有幾種邀請碰友的方法。

Input：

輸入資料的第一行有一個整數 t，代表測資的筆數。

每一筆測試資料的第一行有一個整數 n，代表瀚瀚的好友數量。
接下來有 n 個數字 a₁, a₂, ..., a_n，分別代表每個人討厭的人的編號。

限制：
t ≤ 10
2 ≤ n ≤ 100000
i ≠ a_i (沒有人會討厭自己)

其中 30% 的測試資料滿足： n ≤ 20
其中 70% 的測試資料滿足： n ≤ 2000

Output：

對於每一筆測試資料，請輸出一行，包含一個數字，代表瀚瀚有幾種邀請別人來7122的方法。
由於方法數可能很大，請輸出除以 1000000007 的餘數。

Sample Input：

3
4
2 3 4 1
3
2 1 2
2
2 1

Sample Output：

7
5
3

HINT：

我們用 {...} 來表示邀請到哪些人。

第一筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}, {3}, {4}, {1,3}, {2,4}，共七種

第二筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}, {3}, {1,3}

第三筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}

Source：

Codechef

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0	2000ms	131072kb
1	2000ms	131072kb	10
2	2000ms	131072kb	10
3	2000ms	131072kb	10
4	2000ms	131072kb	10
5	2000ms	131072kb	10
6	2000ms	131072kb	10
7	2000ms	131072kb	10
8	2000ms	131072kb	10
9	2000ms	131072kb	10
10	2000ms	131072kb	10

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。