#P17855. [Ontak2019]POD

[Ontak2019]POD

— 末日旅程

给定两个整数序列 a1,…,ana_1,\ldots,a_n 和 b1,…,bmb_1,\ldots,b_m。求一个最长的公共子序列,使其中任意两个相邻元素的二进制表示至多有 kk 位不同。

也就是说,若所选公共子序列为 x1,…,xtx_1,\ldots,x_t,则对每个 1≤i<t1\le i<t,必须有

$$\operatorname{popcount}(x_i\mathbin{\mathrm{xor}}x_{i+1})\le k.$$

子序列保持原序列中的先后顺序,但不要求连续。长度为0或1的序列自动满足相邻元素限制。

输入格式

第一行三个整数 n,m,kn,m,k。

第二行 nn 个整数,描述序列 aa。第三行 mm 个整数,描述序列 bb。

输出格式

输出一个整数,表示满足条件的最长公共子序列长度。

数据范围

1≤n,m≤200001\le n,m\le20000,0≤k≤310\le k\le31,0≤ai,bj≤2300\le a_i,b_j\le2^{30}。注意上界 2302^{30} 本身也允许出现。

内存限制仅为 32 MB。

子任务 附加限制 分值
1 k=0k=0 5
2 k=1k=1,n,m≤1000n,m\le1000 15
3 n,m≤100n,m\le100
4 n,m≤500n,m\le500
5 n,m≤2000n,m\le2000 40
6 n,m≤10000n,m\le10000 10

原题总约束为20000,而子任务表最大只写到10000;这里保留两者,标程按总约束实现。

样例 1

输入:

3 5 1
1 2 1
2 1 0 1073741824 1

输出:

2