[POI2009]Prz

Time Limit:10000MS  Memory Limit:165536K
Total Submit:16 Accepted:1
Case Time Limit:1000MS

Description

你的任务是计算一个函数F(x, y)，其中x和y是两个正整数序列。F的定义如下：

boolean F(x, y)

if W(x) ≠ W(y) then return 0

else if |W(x)| = |W(y)| = 1 then return 1

else return F(p(x), p(y)) AND F(s(x), s(y)).

W(x)表示序列x中元素的集合。（元素的顺序和出现次数将被无视）

p(x)表示序列x的最长前缀，满足：W(x) ≠ W(p(x))

s(x)表示序列x的最长后缀。满足：W(x) ≠ W(s(x))

|Z|表示集合Z中元素个数

Input

第一行k表示数据组数。
对于每组数据，第一行n,m分别表示x序列的长度与y序列的长度，第二行n个数表示xi，第三行m个数表示yi
1<=k<=13
1<=n,m<=100000
1<=xi,yi<=100

Output

k行，对于每组数据，若F(x,y)为真输出1，否则输出0。

Sample Input

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

Sample Output

0
1

Hint

感谢MT大牛贡献译文.

Source

这个题。。。。额。。非常恶心。。
首先找规律是要悲剧的囧。。。我弄了半天毫无成效。。
然后想的就是DP。。。。
比如说F(l1,r1,l2,r2)表示X的l到r，Y的l2到r2是否匹配。。
然后Prefix和Suffix都可以预处理。所以就是N^4。。无压力TLE
然后注意到两个字串中的不同数的数量肯定是一样的。。//就是W
然后F(l1,l2,num)表示X从l1开始，Y从l2开始。。都是num个不同的字符。。是否匹配。。？
设K=100
N^2*K。。。无压力TLE。。
然后注意到这个是检查是否相等。。所以可以用Hash。。
就是把它的prefix和suffix随便Hash一下。。然后两个判断X和Y是否相等。。
这样的话要考虑如何算Prefix。。如果预处理每个一位到下一个每种数的最近值（前和后）。。？
可以在O（K）的时间搞定Prefix和Suffix。。
然后就可以在N*K^2的时间搞定Hash。。。
然后再考虑如果对每一位的信息进行排序。。
可以做到O（LogK）的时间搞定Prefix和Suffix。。就是N*K*LogK
我现在写的就是这样。。TLE的非常严重。。但是我发现我写的这样要比
标程快很多瀑布汗。。。root的时限好紧啊囧。。。
然后接下来还是可以优化。。不过七夕节到了有别的事要忙就先不写了囧。。。。
如果用扫描的办法可以在N*K的时间内算出所有Prefix和Suffix。。然后
复杂度就是N*K了。。应该可以AC吧囧。。。
终于AC。。泪流满面。。。