Description：

给两个串，每个串由若干数字组成，可以翻转某个数字的最后一位，问最少需要翻转几次是的存在一个位置可以匹配，求出匹配的位置和翻转的位的个数。

$1\leqslant n\leqslant 250000$

Solution：

先对前 $l-1$ 位形成的串跑 $KMP$ ，得到可能匹配的位置，就可以不用管前几位了，构造一个函数： $$ c[i]=\sum_{k=0}^i(a[i-k]-b^R[k])^2 $$ 拆开后显然是两个平方和一个卷积，于是直接求就好了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 2000010

int rd2()

{

	register char c = getchar();

	register int res = 0;

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) | (c - '0');

		c = getchar();

	}

	return res;

}

int x[MAXN],y[MAXN];

int sx[MAXN],sy[MAXN];

struct comp

{

	double r,i;

}a[MAXN],b[MAXN],c[MAXN];

comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

int rev[MAXN];

const double PI = acos(-1);

void FFT(comp f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		comp wn = (comp){cos(-type * 2 * PI / i),sin(-type * 2 * PI / i)};

		for(int j = 0;j < l;j += i)

		{

			comp w = (comp){1,0};

			for(int k = j;k < j + i / 2;++k)

			{

				comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i].r /= l;

	}

	return;

}

int s[MAXN],t[MAXN];

int nxt[MAXN];

int res[MAXN];

pair<int,int> ans;

int main()

{

	scanf("%d%d",&n,&m);

	if(m > n)

	{

		cout << "No" << endl;

		return 0;

	}

	for(int i = 1;i <= n;++i)x[i] = rd2();

	for(int i = 1;i <= m;++i)y[i] = rd2();

	for(int i = 0;i < n;++i)a[i].r = x[i + 1] & 1;

	for(int i = 0;i < m;++i)b[m - 1 - i].r = y[i + 1] & 1;

	for(int i = 0;i < n;++i)sx[i] = sx[i - 1] + a[i].r;

	for(int i = 0;i < m;++i)sy[i] = sy[i - 1] + b[i].r;

	int l = 0,len = 1;

	for(;len <= (n + m) * 2;len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	FFT(a,len,1);FFT(b,len,1);

	for(int i = 0;i < len;++i)c[i] = a[i] * b[i];

	FFT(c,len,-1);

	for(int i = m - 1;i < n;++i)

	{

		c[i].r = c[i].r * (-2);

		c[i].r += sx[i] - sx[i - m] + sy[m - 1];

	}

	for(int i = m;i <= n;++i)res[i] = int(c[i - 1].r + 0.5);

	ans.first = ans.second = 0x3f3f3f3f;

	for(int i = 1;i <= n;++i)s[i] = x[i] >> 1;

	for(int i = 1;i <= m;++i)t[i] = y[i] >> 1;

	for(int i = 2,j = 0;i <= m;++i)

	{

		while(j && t[j + 1] != t[i])j = nxt[j];

		if(t[j + 1] == t[i])++j;

		nxt[i] = j;

	}

	for(int i = 1,j = 0;i <= n;++i)

	{

		while(j && t[j + 1] != s[i])j = nxt[j];

		if(t[j + 1] == s[i])++j;

		if(i >= m && j == m)

		{

			ans = min(ans,make_pair(res[i],i - m + 1));

		}

	}

	if(ans.first == 0x3f3f3f3f)cout << "No" << endl;

	else cout << "Yes" << endl << ans.first << " " << ans.second << endl;

	return 0;

}