# 【日常小测】图片加密

### 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];

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;
}

static char pat; 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 = -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] = 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] = 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() {
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];

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;
}


## 23 thoughts to “【日常小测】图片加密”

1. tinyurl.com说道：

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!

2. ps4 games说道：

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.

3. quest bars cheap说道：

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.

4. quest bars cheap说道：

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!

5. quest bars cheap coupon twitter说道：

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?

6. quest bars cheap coupon twitter说道：

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.

7. quest bars cheap说道：

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.

8. ps4 games说道：

A theme like yours with a few simple tweeks would really make my blog jump out.
it

9. ps4 games说道：

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!

10. quest bars cheap说道：

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.

11. ps4 games说道：

Hi there, after reading this amazing piece of
writing i am too delighted to share my knowledge here with
friends.

12. oprol evorter说道：

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!

13. coconut oil说道：

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.

14. match.com free trial说道：

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!

15. match.com free trial说道：

I think the admin of this website is genuinely working
hard in support of his site, since here every stuff is quality
based data.

16. tinyurl.com说道：

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!

17. sling tv说道：

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!

18. If some one wants expert view concerning blogging then i propose him/her to pay
a visit this weblog, Keep up the fastidious job.

19. sling tv说道：

Howdy! This blog post couldn’t be written much better!

Fairly certain he’ll have a good read. Thank you for sharing!

20. sling tv说道：

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

21. sling tv说道：

Inspiring quest there. What happened after? Good luck!

22. sling tv best package 2020说道：

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!

23. Maryanna Bubis说道：

Your place is valueble for me. Thanks!…