Problem : 309 - Algorithm Speedup

Problem Statistics

Solved Member: 2　　Submission: 15　　User Tried: 3

Statement:

請你計算F(x,y)的值，其中x,y皆是一個數列，x=(x₁,x₂...x_n),y=(y₁,y₂...y_m)。

Boolean F(x,y)
{
　　if W(x) ≠ W(y)
　　　　return 0
　　else if |W(x)| = |W(y)| = 1
　　　　return 1
　　else
　　　　return F(p(x),p(y)) ^ F(s(x),s(y))
}

其中：

•W(x)為數列x的數字集合 (每種數字的個數與順序不重要)
•p(x)為數列x的最長前綴，並滿足W(x) ≠ W(p(x))
•s(x)為數列x的最長後綴，並滿足W(x) ≠ W(s(x))
• ^ 為Boolean運算，A ^ B = 1 唯若且若 A,B 皆為 True
•|W(x)|為數列x的數字種類

例如，若x=(2,3,7,2,7,4,7,2,4)，則W(x)={2,3,4,7}，p(x)=(2,3,7,2,7)，s(x)=(7,2,7,4,7,2,4)，|W(x)|=4。

由於遞迴計算F(x,y)太慢了，請你想辦法使他計算更快，每筆測試資料會給定x,y數列，請你輸出F(x,y)。

Input:Output:

第一行為k (1 ≤ k ≤ 13)，表示共有 k 筆測試資料。

每筆測試資料佔三行，第一行為n,m (1 ≤ n,m ≤ 100000)，分別表示x數列與y數列的長度，第二行有n個數字表示x數列，第三行有m個數字表示y數列，數列的值皆不大於100。

對於一筆測試資料輸出一行0或1。

Sample Input:Sample Output:

2
4 5
3 1 2 1
1 3 1 2 1
7 7
1 1 2 1 2 1 3
1 1 2 1 3 1 3

0
1

Source:

POI 16 Stage 1

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
5	12000ms	65536kb	10
6	12000ms	65536kb	10
7	12000ms	65536kb	10
8	12000ms	65536kb	10
9	12000ms	65536kb	10
10	12000ms	65536kb	10