2015
09-17

# Jinkeloid

After listening several songs of Jinkeloid,I come up with this problem :).
There is a string s only consist of first 20 lowercase English letters.
And we have several queries,each time I have k letters c1, c2, …, ck,and I wonder how many consecutive substring of string s that each ci has occur even times in it.
Two substring with the same content but different position are considered different.

The first line contains integer T(1<=T<=5),denote the number of the test cases.
For each test cases,the first line contains a string s(1<= length of s <= 105),the second line contains a number Q (Q<= 3 * 104),denote the number of queries.
Then Q lines follows,each lines start with a number k(1<= k<= 5),then contains k lowercase English letters c1, c2, …, ck(There won’t be duplicated ci).

The first line contains integer T(1<=T<=5),denote the number of the test cases.
For each test cases,the first line contains a string s(1<= length of s <= 105),the second line contains a number Q (Q<= 3 * 104),denote the number of queries.
Then Q lines follows,each lines start with a number k(1<= k<= 5),then contains k lowercase English letters c1, c2, …, ck(There won’t be duplicated ci).

1
cacca
5
3 c a b
2 c b
2 a b
3 c b a
2 a b

2
7
6
2
6
Hint
Remember 0 is also a even number,so occur zero times is ok.
Thanks Jinkeloid for this problem :).


        for(int j = 0; j < 20; j++) {
for(int i = 0; i < 1<<20; i++) if(i>>j&1) {
cnt[i^(1<<j)] += cnt[i];
}
}