题目大意
给定两个数字串$A,B$,长度分别为$n,m(m \le n \le 250000)$
串中的元素为$<512$的自然数,你可以花费一个单位的代价改变一个元素在二进制下的最低位
询问能否通过修改操作使得$B$在$A$中出现
如果可以,请输出最小的花费和在花费最小的前提下最左边的匹配位置
解题报告
我们发现高位不可改,于是我们用$KMP$统计一下高位的合法位置
至于低位,我们可以拆成两次$FFT$
于是搞一搞就可以了
至于为什么我写的是$SA$?
因为考场上忘掉$KMP$怎么写了 QwQ
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 550000; const int M = N << 1; const int INF = 1e9; const int MOD = 1004535809; int n,m,L,a1[M],a2[N],o1[N],o2[N],leg[N],ans[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int Read() { static char pat[20]; scanf("%s",pat+1); int ret = 0; for (int i=8,w=1;i;i--,w<<=1) ret += (pat[i]-'0') * w; return ret; } class Suffix_Array{ int len,tot,*rak,*que,bot[N],sa[M],arr1[M],arr2[M],height[N]; public: inline void build() { rak = arr1; que = arr2; len = n + m + 1; a1[0] = -1; a1[len+1] = -2; for (int i=1;i<=len;i++) ++bot[a1[i]]; for (int i=1;i<=100000;i++) bot[i] += bot[i-1]; for (int i=1;i<=len;i++) sa[bot[a1[i]]--] = i; rak[sa[1]] = tot = 1; for (int i=2;i<=len;i++) rak[sa[i]] = (a1[sa[i]]==a1[sa[i-1]])? tot: ++tot; for (int l=1,cnt;cnt=0,l<=len;l<<=1) { for (int i=len-l+1;i<=len;i++) que[++cnt] = i; for (int i=1;i<=len;i++) if (sa[i]>l) que[++cnt] = sa[i] - l; for (int i=0;i<=tot;i++) bot[i] = 0; for (int i=1;i<=len;i++) bot[rak[i]]++; for (int i=1;i<=tot;i++) bot[i] += bot[i-1]; for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i]; swap(que, rak); rak[sa[1]] = tot = 1; for (int i=2;i<=len;i++) if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]] = tot; else rak[sa[i]] = ++tot; if (tot >= len) break; } GetHeight(); } inline void solve() { for (int i=rak[n+2];height[i]>=m;i--) if (sa[i] <= n) leg[sa[i]] = 1; for (int i=rak[n+2]+1;height[i]>=m;i++) if (sa[i] <= n) leg[sa[i]] = 1; } private: inline void GetHeight() { for (int i=1;i<=len;i++) { int len = max(0, height[rak[i-1]] - 1); int p1 = i + len, p2 = sa[rak[i]-1] + len; while (a1[p1++] == a1[p2++]) len++; height[rak[i]] = len; } } }SA; class Number_Theoretic_Transform{ int pos[M],REV,G; public: inline void init() { for (L=1;L<n+m;L<<=1); G = 3; int len = 1,tt=-1; while (len < L) len<<=1, ++tt; REV = Pow(L, MOD-2); for (int i=1;i<len;i++) pos[i] = (pos[i>>1]>>1)|((1<<tt)*(i&1)); } inline void trans(int *a, int t=1) { for (int i=0;i<L;i++) if (pos[i] < i) swap(a[pos[i]], a[i]); for (int l=2;l<=L;l<<=1) { int wn = Pow(G, MOD/l); if (t == -1) wn = Pow(wn, MOD-2); for (int i=0;i<L;i+=l) { for (int j=0,w=1;j<l/2;j++,w=(LL)w*wn%MOD) { int tmp = (LL)w * a[i+l/2+j] % MOD; a[i+l/2+j] = (a[i+j] - tmp) % MOD; a[i+j] = (a[i+j] + tmp) % MOD; } } } if (t == -1) for (int i=0,rev=Pow(L,MOD-2);i<L;i++) a[i] = (LL)a[i] * rev % MOD; for (int i=0;i<L;i++) a[i] = a[i]<0? a[i] + MOD: a[i]; } private: inline int Pow(int w, int t) { int ret = 1; for (;t;t>>=1,w=(LL)w*w%MOD) if (t&1) ret=(LL)ret*w%MOD; return ret; } }NTT; int main() { n = read(); m = read(); for (int i=1;i<=n;i++) a1[i] = o1[i] = Read(); for (int i=1;i<=m;i++) a2[i] = o2[i] = Read(); //find out legal positions for (int i=1;i<=m;i++) a1[n+i+1] = a2[i]; for (int i=1;i<=n+m+1;i++) a1[i] >>= 1, a1[i]++; a1[n+1] = 0; SA.build(); SA.solve(); //calculate the cost NTT.init(); memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2)); for (int i=0;i<n;i++) a1[i] = o1[i+1] & 1; for (int i=0;i<m;i++) a2[i] = (o2[m-i] & 1) ^ 1; NTT.trans(a1); NTT.trans(a2); for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD; NTT.trans(a1, -1); for (int i=1;i<=n;i++) ans[i] = a1[i+m-2]; memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2)); for (int i=0;i<n;i++) a1[i] = (o1[i+1] & 1) ^ 1; for (int i=0;i<m;i++) a2[i] = o2[m-i] & 1; NTT.trans(a1); NTT.trans(a2); for (int i=0;i<L;i++) a1[i] = (LL)a1[i] * a2[i] % MOD; NTT.trans(a1, -1); for (int i=1;i<=n;i++) ans[i] += a1[i+m-2]; //output the answer int pos=-1, cost=INF; for (int i=1;i<=n;i++) if (leg[i] && ans[i] < cost) cost = ans[i], pos = i; if (!~pos) puts("No"); else printf("Yes\n%d %d\n",cost,pos); return 0; }