2016年2月25日 星期四

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

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/300_files/extensions/MathMenu.js
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,會有一個特定討厭的碰友 ai,代表瀚瀚不能同時邀請 i 與 ai 兩個人,否則他們會打架,瀚瀚就7122不出來了。

請你找出瀚瀚有幾種邀請碰友的方法。
Input:
輸入資料的第一行有一個整數 t,代表測資的筆數。

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

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

其中 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:
TestTimeMemoryScore
02000ms131072kb
12000ms131072kb10
22000ms131072kb10
32000ms131072kb10
42000ms131072kb10
52000ms131072kb10
62000ms131072kb10
72000ms131072kb10
82000ms131072kb10
92000ms131072kb10
102000ms131072kb10

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原