题目大意
给定两个数字串$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; }
What i don’t realize is if truth be told how you
are no longer actually a lot more neatly-appreciated than you
may be right now. You’re very intelligent. You recognize thus considerably relating to this
topic, made me individually consider it from so
many various angles. Its like women and men are not interested unless
it is something to do with Woman gaga! Your own stuffs nice.
Always handle it up!
If some one wants expert view about blogging and site-building then i recommend him/her to go to see this
blog, Keep up the nice work.
Wonderful beat ! I would like to apprentice while you
amend your website, how can i subscribe for a blog
web site? The account helped me a acceptable deal.
I had been tiny bit acquainted of this your broadcast offered bright clear concept
Hi there! Do you know if they make any plugins to
help with SEO? I’m trying to get my blog to rank for some targeted keywords but
I’m not seeing very good success. If you know of any please share.
Thanks!
Right now it seems like Drupal is the best
blogging platform out there right now. (from what I’ve read) Is that what you’re using on your
blog?
Have you ever considered creating an ebook or guest authoring on other sites?
I have a blog based upon on the same topics you discuss and would love to have you share some stories/information. I
know my audience would appreciate your work.
If you’re even remotely interested, feel free to send me an e mail.
I have learn some just right stuff here. Definitely price bookmarking for revisiting.
I wonder how much attempt you place to make one of these great
informative site.
Interesting blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple tweeks would really make my blog jump out.
Please let me know where you got your design. Appreciate
it
you’re really a just right webmaster. The web site loading speed is incredible.
It kind of feels that you’re doing any unique trick.
Furthermore, The contents are masterpiece. you have
done a fantastic activity on this matter!
Hello everyone, it’s my first pay a quick visit at this site, and article is in fact fruitful designed for me, keep up posting such articles.
Hi there, after reading this amazing piece of
writing i am too delighted to share my knowledge here with
friends.
Having read this I thought it was very informative. I appreciate you taking the time and effort to put this article together. I once again find myself spending way to much time both reading and commenting. But so what, it was still worth it!
Hello There. I found your blog using msn. This is a very
well written article. I’ll make sure to bookmark
it and come back to read more of your useful info. Thanks for the post.
I will definitely return.
You actually make it appear really easy along with your presentation but I to find
this matter to be really something which I feel I might never understand.
It sort of feels too complicated and extremely huge for
me. I am looking ahead on your subsequent post, I will attempt to get the cling of it!
I think the admin of this website is genuinely working
hard in support of his site, since here every stuff is quality
based data.
Wow that was unusual. I just wrote an extremely long comment but
after I clicked submit my comment didn’t show up. Grrrr…
well I’m not writing all that over again. Anyway, just
wanted to say superb blog!
I like the helpful information you supply for your articles.
I will bookmark your weblog and check once more here regularly.
I am reasonably sure I will be told lots of new stuff proper here!
Best of luck for the following!
If some one wants expert view concerning blogging then i propose him/her to pay
a visit this weblog, Keep up the fastidious job.
Howdy! This blog post couldn’t be written much better!
Looking at this article reminds me of my previous roommate!
He constantly kept talking about this. I am going to forward this article to him.
Fairly certain he’ll have a good read. Thank you for sharing!
Hey there! Would you mind if I share your blog with my twitter group?
There’s a lot of folks that I think would really enjoy your content.
Please let me know. Thank you
Inspiring quest there. What happened after? Good luck!
You really make it seem really easy together with your
presentation however I in finding this matter to be really something which I feel I would never understand.
It kind of feels too complex and very wide for me.
I am taking a look ahead on your next publish, I’ll try to
get the grasp of it!
Your place is valueble for me. Thanks!…