【日常小测】图片加密

题目大意

给定两个数字串$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;
}

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

  1. 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. 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

  3. 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!

  4. 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.

  5. 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

  6. 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!

  7. 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!

  8. 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.

  9. 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!

  10. 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!

  11. 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!

  12. 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!

  13. 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

  14. 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!

发表评论

电子邮件地址不会被公开。 必填项已用*标注