URAL1966 Cipher Message 3

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描述

题解：

能看出来的是，每一组数只能改最后一位，所以前$7$位动不了。

所以$KMP$跑一跑。

重点在于最后一位怎么搞。

如果$KMP$跑完了还没找到合适的位置，直接$puts("No")$就好了。

剩下个匹配问题。

（要不是数据范围拦着我我都想建图跑费用流了）

这个匹配可以用$FFT$求。

$FFT$不是求$\sum(a[i]*b[j-i])$的吗？怎么求字符串匹配？

其实我们只想要最后多项式中某一位上的值，所以$b[j-i]$和$b[i]$没有区别，反转数组就好了。

我们要求的是需要多少个$0$变成$1$，以及多少个$1$变成$0$。

所以$FFT$求两遍卷积，第一次$a[i]=[s1[i]==0],b[i]=[s2[i]==1]$，注意这里的$b$还没有反转。

第二次反过来就可以了。

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef unsigned long long ull;

const int N = ;

const ull seed = ;

const double Pi = acos(-1.0);

template<typename T>

inline void read(T&x)

{

    T f = ,c = ;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

struct cp

{

    double x,y;

    cp(){}

    cp(double x,double y):x(x),y(y){}

    cp operator + (const cp&a)const{return cp(x+a.x,y+a.y);}

    cp operator - (const cp&a)const{return cp(x-a.x,y-a.y);}

    cp operator * (const cp&a)const{return cp(x*a.x-y*a.y,x*a.y+y*a.x);}

};

int to[*N],lim=,l;

void fft(cp *a,int len,int k)

{

    for(int i=;i<len;i++)

        if(i<to[i])swap(a[i],a[to[i]]);

    for(int i=;i<len;i<<=)

    {

        cp w0(cos(Pi/i),k*sin(Pi/i));

        for(int j=;j<len;j+=(i<<))

        {

            cp w(,);

            for(int o=;o<i;o++,w=w*w0)

            {

                cp w1 = a[j+o],w2 = a[j+o+i]*w;

                a[j+o] = w1+w2;

                a[j+o+i] = w1-w2;

            }

        }

    }

    if(k==-)

        for(int i=;i<len;i++)

            a[i].x/=len;

}

void rd(int n,int *a1,int *a2)

{

    for(int x,i=;i<=n;i++)

    {

        read(x);

        a1[i] = x%;

        a2[i] = x/;

    }

}

int n,m,a[][N],b[][N];

bool vis[N];

int ans[N];

cp c1[*N],c2[*N],c3[*N];

int nxt[N];

void get_nxt(int *a,int len)

{

    int i = ,j = ;

    while(i<=len)

    {

        if(!j||a[i]==a[j])

        {

            i++,j++;

            nxt[i] = j;

        }else j = nxt[j];

    }

}

int kmp(int *a,int la,int *b,int lb)

{

    int ret = ;

    int i = ,j = ;

    while(i<=la)

    {

        if(a[i]==b[j]||j==)

        {

            i++,j++;

            if(j==lb+)

            {

                vis[i-]=;

                j = nxt[j];

                ret = ;

            }

        }else j=nxt[j];

    }

    return ret;

}

void work()

{

    fft(c1,lim,),fft(c2,lim,);

    for(int i=;i<lim;i++)c3[i]=c1[i]*c2[i];

    fft(c3,lim,-);

}

void init()

{

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    memset(ans,,sizeof(ans));

    memset(vis,,sizeof(vis));

    lim=,l=;

}

int main()

{

//    freopen("tt.in","r",stdin);

    while(scanf("%d%d",&n,&m)>)

    {

    init();

    rd(n,a[],a[]),rd(m,b[],b[]);

    get_nxt(b[],m);

    if(!kmp(a[],n,b[],m))

    {

        puts("No");

        continue;

    }

    puts("Yes");

    while(lim<*(n+m))lim<<=,l++;

    for(int i=;i<lim;i++)to[i]=((to[i>>]>>)|((i&)<<(l-)));

    for(int i=;i<lim;i++)c1[i]=c2[i]=cp(,);

    for(int i=;i<n;i++)c1[i].x=(a[][i+]==);

    for(int i=;i<m;i++)c2[i].x=(b[][m-i]==);

    work();

    for(int i=;i<n;i++)ans[i+]=(int)(c3[i].x+0.5);

    for(int i=;i<lim;i++)c1[i]=c2[i]=cp(,);

    for(int i=;i<n;i++)c1[i].x=(a[][i+]==);

    for(int i=;i<m;i++)c2[i].x=(b[][m-i]==);

    work();

    for(int i=;i<n;i++)ans[i+]+=(int)(c3[i].x+0.5);

    int mn = N,pos=;

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

        if(vis[i]&&ans[i]<mn)

        {

            mn = ans[i];

            pos = i-m+;

        }

    printf("%d %d\n",mn,pos);

    }

    return ;

}