#P12876. Cut Check Bit

    ID: 12062 传统题 5000ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-暴力枚举线性 DP前后缀最值增量维护2025“钉耙编程”中国大学生算法设计暑期联赛(10)

Cut Check Bit

Cut Check Bit

Problem Description

温馨提示:请注意你代码的空间常数。 给定一个长为 nn 的非负整数序列 aa,和一个常数 xx。 你需要把 aa 划分成若干段,使得「每一段的按位与」的按位或 ≤x\le x。 你需要最大化划分成的段数,或者报告无解。

Input

本题有多组数据。第一行一个正整数 TT(1≤T≤1041\le T\le10^4)表示数据组数。对于每组测试数据: 第一行输入两个正整数 n,mn,m(1≤n,m,n⋅m≤4⋅1061\le n,m,n\cdot m\le4\cdot 10^6),其中 mm 的作用如下: 为了减少读入量,序列 aa 和常数 xx 以 3232 进制的方式输入。具体的,给出的是长度恰好为 mm 的,只包含数字 0∼9\texttt{0}\sim\texttt{9} 和小写字母 a∼v\texttt{a}\sim\texttt{v} 的字符串(a\texttt{a} 代表 1010,b\texttt{b} 代表 1111,以此类推,可能有前导 0\texttt{0}),其真实值即为该字符串转换为 3232 进制得到的数。显然这样输入的数 ∈[0,32m)\in[0,32^m)。 第二行以上述方式输入常数 xx。 第三行以上述方式输入序列 aa,相邻字符串之间恰有一个空格隔开。 保证 ∑n⋅m≤2⋅107\sum n\cdot m\le2\cdot10^7。

Output

对于每组数据,若有解,则输出最大的划分出的段数;若无解,输出 −1-1。

Sample Input

3
4 1
2
3 1 4 2
1 3
lct
sam
3 1
t
6 h c

Sample Output

2
-1
2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(10)