#P12850. 最完全的替换

    ID: 12036 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 3 上传者: 标签>CF1300贪心模拟字符串2025“钉耙编程”中国大学生算法设计暑期联赛(8)

最完全的替换

最完全的替换

Problem Description

小 E 拿到了长度分别为 n,mn, m 的 01 串,分别记为 ss 和 tt,保证 m≤nm\leq n。 小 E 每次操作可以:

  • 选择 ss 的任意一个长度为 mm 的子串 s[i,i+m−1]s[i, i+m-1],满足 1≤i≤i+m−1≤n1\leq i\leq i +m-1\leq n。
  • 将这个子串替换为 它与 tt 异或后的结果。
  • 即 ∀j=1,2,⋯ ,m\forall j=1,2,\cdots, m,将 s[i+j−1]s[i+j-1] 替换为 s[i+j−1]⊕t[j]s[i+j-1]\oplus t[j],其中 ⊕\oplus 为异或操作(c++ 中的 ^)。 小 E 想知道,最少多少次操作可以把 ss 变为一个全 0 串。 如果小 E 永远无法做到,输出 -1。

Input

本题有多组测试数据。第一行一个正整数 TT,表示数据组数,接下来输入每组测试数据。 对于每组测试数据:

  • 第一行,两个正整数 n,mn,m,分别表示 ss 与 tt 的长度。
  • 第二行,长度为 nn 的 01 字符串 s。
  • 第三行,长度为 mm 的 01 字符串 t。

Output

对于每组测试数据,输出一行一个整数,表示最少操作次数。如果无法做到替换为全 0 串,则输出 -1。

Sample Input

1
5 3
10100
110

Sample Output

2

Hint

对于所有测试数据:1≤T≤501\leq T\leq 50,2≤n≤1052\leq n\leq 10^5,1≤m≤301\leq m\leq 30。

Source

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