Problem : 397 - 猜數列

Problem Statistics

Solved Member: 19　　Submission: 99　　User Tried: 20

Statement:

你有聽過「猜數列遊戲」嗎？

也許沒有，不過，某条瘋狂愛上這款遊戲。

猜數列遊戲的一開始，會先生成一個長度為 N 的數列，並且將這個數列無限重複，當作地圖。
接下來，玩家將被指派一個長度為 M 的數列，當作密碼。

玩家將不被給予任何線索的任意選擇一個點當作起始點，也就是說這個無限大的地圖上，所有點被選到的機率是相等的。
從起始點開始，將密碼和地圖對齊，依序將數列的每一項互相比對，每比對到一項就加一分。

第一筆範例測資中的兩個數列是

6 3 1 2 6
1 2 6 6

因此，該地圖為

6 3 1 2 6 6 3 1 2 6 6 ...

當某条選擇從第一個位置開始，那麼他將得到 0 分。（6 3 1 2 和 1 2 6 6 比對）
從第二個位置開始，他將得到 1 分。（3 1 2 6 和 1 2 6 6 比對）
從第三個位置開始，他就可以得到 4 分。（1 2 6 6 和 1 2 6 6 比對）

現在某条想要問你，在給定地圖和密碼的情況下，某条拿到恰好 M 分的機率是多少？

Input:Output:

輸入的第一行有兩個正整數 N、M，分別代表地圖的生成數列長度和密碼長度。
第二行有 N 個數字 A_i，為地圖的生成數列。
第三行有 M 個數字 B_j，為密碼的數列。

1 ≤ N, M ≤ 1000000
0 ≤ A_i, B_j ≤ 1000000000

在佔分 50% 的測試資料中，我們保證 1 ≤ N, M ≤ 1000, 1 ≤ A_i, B_j ≤ 5。

請輸出一行，代表恰得到 M 分的機率。
機率請以 q / p 表示，其中 p 和 q 都要是正整數，且 GCD(p,q) = 1。
這個機率有可能會是 0 ，當機率為 0 時請輸出 "QAQ"。（不含引號）

Sample Input:Sample Output:

Case #1:
5 4
6 3 1 2 6
1 2 6 6

Case #2:
4 2
1 2 3 5
8 13

Case #1:
1/5

Case #2:
QAQ

Source:

104資奧校內初選

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
1-1	500ms	262144kb	50
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
1-11	500ms	262144kb
1-12	500ms	262144kb
1-13	500ms	262144kb
1-14	500ms	262144kb
1-15	500ms	262144kb
1-16	500ms	262144kb
1-17	500ms	262144kb
1-18	500ms	262144kb
1-19	500ms	262144kb
1-20	500ms	262144kb
1-21	1000ms	262144kb
1-22	1000ms	262144kb
1-23	1000ms	262144kb
1-24	1000ms	262144kb
1-25	2000ms	262144kb
2-1	500ms	262144kb	50
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
2-9	500ms	262144kb
2-10	500ms	262144kb
2-11	1000ms	262144kb
2-12	1000ms	262144kb
2-13	1000ms	262144kb
2-14	1000ms	262144kb
2-15	1000ms	262144kb
2-16	1000ms	262144kb
2-17	1000ms	262144kb
2-18	1000ms	262144kb
2-19	1000ms	262144kb
2-20	1000ms	262144kb
2-21	1000ms	262144kb
2-22	1000ms	262144kb
2-23	1000ms	262144kb
2-24	1000ms	262144kb
2-25	2000ms	262144kb