[数据结构与算法]fft（快速傅里叶变换）

模板
从 A(x)=$a_0+a_{1}x+a_2{x}^2+a_3{x}^3$理解更加简单
我们可以把A(x)用4个顶点来表示，此时他一定是唯一确定的曲线，易证。
四个顶点分别取单位根，那么我们要计算A($w_4^0$),A($w_4^1$),A($w_4^2$),A($w_4^3$)
分奇偶
a(x)=$a_0+a_{2}x$
b(x)=$a_1+a_{3}x$
易得A(x)=a($x^2$)+x*b($x^2$)
计算k个单位根下的值,我们把k分成k<$\frac{n}{2}$和k>=$\frac{n}{2}$
k<$\frac{n}{2}$,A($w_n^k$)=a($w_{\frac{n}{2}}^k$)+$w_n^k$*b($w_{\frac{n}{2}}^k$)
t>=$\frac{n}{2}$,k+$\frac{n}{2}$=t,A($w_n^t$)=a($w_{\frac{n}{2}}^k$)-$w_n^k$*b($w_{\frac{n}{2}}^k$)
原始a中的元素在换位后，第i个位置的值为A($W_1^0$)=a[rev[i]]

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const double PI=acos(-1);
int n,m;
struct Complex
{
    double x,y;
    Complex operator +(const Complex& t)const
    {
        return {x+t.x,y+t.y};
    }
    Complex operator -(const Complex& t)const 
    {
        return {x-t.x,y-t.y};
    }
    Complex operator *(const Complex& t)const 
    {
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[N],b[N];
int rev[N],tot,bit;
void fft(Complex a[], int inv)
{
    for(int i=0;i<tot;i++)
    {
        if(i<rev[i])
        {
            swap(a[i],a[rev[i]]);
        }
    }
    for(int mid=1;mid<tot;mid<<=1)//此时是在倒数第二层，正在合并
    {
        auto w1=(Complex{cos(PI/mid),(inv)*sin(PI/mid)});//计算长度为2*mid的wk
        for(int i=0;i<tot;i+=2*mid)
        {
            auto wk=(Complex{1,0});
            for(int j=0;j<mid;j++,wk=wk*w1)//只需要求一半的wk即可
            {
                auto x=a[i+j],y=wk*a[i+j+mid];
                a[i+j]=x+y;
                a[i+j+mid]=x-y;
            }
        }
    }
    
}
int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)scanf("%lf",&a[i].x);
    for(int i=0;i<=m;i++)scanf("%lf",&b[i].x);
    while(1<<(bit)<n+m+1)bit++;
    tot=1<<bit;//tot大于等于系数的个数
    for(int i=0;i<tot;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    }//本质上是将二进制数倒置，dp易推
    fft(a,1);
    fft(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i];//实际上a[i]放的是n次单位根的结果
    fft(a,-1);
    for(int i=0;i<=n+m;i++)
    {
        printf("%d ",(int)(a[i].x/tot+0.5));
    }
    return 0;
}

H Hash Function

题意：给n个数，找出最小的seed使得这n个数%seed的结果互不相同,1<=n<=500000.

题解：
其实，a%seed=b%seed，那么有(a-b)=kseed，易证。
(a=k1seed+mod,b=k2*seed+mod,则a-b=(k1-k2）seed=kseed)

这样只要处理出每个数两两的差，差的范围一定是[1,500000]，接着从[1,500000]枚举答案，答案只要满足其所有的倍数不是每个数两两的差即可，复杂度(nlogn)。

怎么处理两两的差值呢，假设给3个数2,3,4,我们考虑多项式f(x)=$x^2+x^3+x^4$，g(x)=$x^{?2}+x^{?3}+x^{?4}$，那么f(x)*g(x)=$3x^0+2x^1+1x^2+2x^{?1}+1x^{?2}$，x指数就是两数的差值，系数大于0表示存在。当然对于指数为负数的多项式我们无法处理，所以我们对g(x)进行平移即可，即令t(x)=$x^{500000}$g(x)，接着计算即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
const double PI=acos(-1);
struct Complex
{
    double x,y;
    Complex operator +(const Complex & t)const
    {
        return Complex{x+t.x,y+t.y};
    }
    Complex operator -(const Complex & t)const
    {
        return Complex{x-t.x,y-t.y};
    }
     Complex operator *(const Complex & t)const
    {
        return {x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[N],b[N];
int tot,bit,n,m,rev[N];
void fft(Complex a[],int inv)
{
    for(int i=0;i<tot;i++)
    {
        if(i<rev[i])
        {
            swap(a[i],a[rev[i]]);
        }
        
    }
    for(int mid=1;mid<tot;mid<<=1)
        {
            Complex wk={cos(PI/mid),inv*(sin(PI/mid))};
            for(int i=0;i<tot;i+=2*mid)
            {
                Complex w1={1,0};
                for(int j=0;j<mid;j++,w1=w1*wk)
                {
                    Complex x=a[i+j],y=w1*a[i+j+mid];
                    a[i+j]=x+y,a[i+j+mid]=x-y;
                }
            }
        }
}
const int M=5e5;
int cnt[M+10];
int t;
int f[M+10];
int main ()
{
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        int num;
        scanf("%d",&num);
        cnt[num]=1;
    }
    int n=M,m=M;
    for(int i=0;i<=M;i++)
    {
        a[i].x=cnt[i];
        b[i].x=cnt[M-i];
    }
    while((1<<bit)<n+m+1)bit++;
    tot=1<<bit;
    for(int i=0;i<tot;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    }
    fft(a,1);
    fft(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=M+1;i<=2*M;i++)
    {
        f[i-M]=(int)(a[i].x/tot+0.5);
        if(f[i-M]>=1)f[i-M]=1;
    }
    for(int i=1;i<=M;i++)
    {
        int flag=1;
         for(int j=1;j*i<=M;j++)
         {
             if(f[i*j])
             {
                 flag=0;
                 break;
             }
         }
        if(flag)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<500001<<endl;
    return 0;
}

Forgiving Matching

题意：给一个由{‘0’-‘9’,’※’}的两个字符串S,T，其长度为n,m.
在S中长度为m的子串与T匹配，某一子串其与T不相同的位置个数记做t，※为万能符号，求k从[0,m]，分别有多少子串满足t<=k

题解：因为字符类型很少，我们可以先不考虑*的影响，对于每一位数字i，从S选一个位置p1,从T选一个位置p2,那么此时两个位置如果相同，则以p1-p2为首的子串此时匹配的成果数+1,从两个数段当中分别取一个数进行组合可以用fft来计算方案数。

考虑※影响，无非就是子串当中自带※，或者T中自带※，我们把他们都加入每个子串的合法位置数，最后还要减去多算的※，也就是某一子串的某一位置刚好与T匹配并且两者都是※的位置数，这个过程也是做一次fft即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const double PI=acos(-1);
struct Complex
{
    double x,y;
    Complex operator+ (const Complex &t)const
    {
        return (Complex){x+t.x,y+t.y};
    }
    Complex operator- (const Complex &t)const
    {
        return (Complex){x-t.x,y-t.y};
    }
    Complex operator* (const Complex &t)const
    {
        return (Complex){x*t.x-y*t.y,x*t.y+y*t.x};
    }
}a[N],b[N];
int tot,bit,rev[N],n,m;
int cnt[N],d[N],k[N];
char  s1[N],s2[N];
void fft(Complex a[],int inv)
{
    for(int i=0;i<tot;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int mid=1;mid<tot;mid<<=1)
    {
        Complex wk={cos(PI/mid),inv*sin(PI/mid)};
        for(int i=0;i<tot;i+=2*mid)
        {
            Complex w1={1,0};
            for(int j=0;j<mid;j++,w1=w1*wk)
            {
                Complex x=a[i+j],y=w1*a[i+j+mid];
                a[i+j]=x+y;
                a[i+j+mid]=x-y;
            }
        }
    }
}
void solve()
{
    scanf("%d%d",&n,&m);
    scanf("%s%s",s1,s2);
    for(int i=0;i<=n-m;i++)cnt[i]=0;
    n--;
    m--;
    while((1<<bit)<n+m+1)bit++;
    tot=1<<bit;
    for(int i=0;i<tot;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    }
    for(int num=0;num<=9;num++)
    {
        for(int i=0;i<=n;i++)
        {
            if(s1[i]==num+'0')
            {
                a[i].x=1;
            }
            else a[i].x=0;
            a[i].y=0;
        }
        for(int i=n+1;i<tot;i++)a[i].x=0,a[i].y=0;
        for(int i=0;i<=m;i++)
        {
            if(s2[m-i]==num+'0')
            {
                b[i].x=1;
            }
            else b[i].x=0;
            b[i].y=0;
        }
        for(int i=m+1;i<tot;i++)b[i].x=0,b[i].y=0;
        fft(a,1),fft(b,1);
        for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
        fft(a,-1);
        for(int i=0;i<=n-m;i++)
        {
            cnt[i]+=(int)(a[i+m].x/tot+0.5);
        }
    }

    int x=0;
    for(int i=0;i<=m;i++)
    {
        if(s2[i]=='*')
        {
            x++;
        }
    }
    for(int i=0;i<=n-m;i++)
    {
        cnt[i]+=x;
    }
    d[n+1]=0;
    for(int i=n;i>=0;i--)
    {
        if(s1[i]=='*')d[i]=d[i+1]+1;
        else d[i]=d[i+1];
    }
    for(int i=0;i<=n-m;i++)
    {
        cnt[i]+=d[i]-d[i+m+1];
    }
    for(int i=0;i<=n;i++)
    {
        if(s1[i]=='*')a[i].x=1;
        else a[i].x=0;
        a[i].y=0;
    }
    for(int i=n+1;i<tot;i++)a[i].y=0,a[i].x=0;
    for(int i=0;i<=m;i++)
    {
        if(s2[m-i]=='*')b[i].x=1;
        else b[i].x=0;
        b[i].y=0;
    }
    for(int i=m+1;i<tot;i++)b[i].x=b[i].y=0;
    fft(a,1);
    fft(b,1);
    for(int i=0;i<tot;i++)a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=0;i<=n-m;i++)
    {
        cnt[i]-=(int)(a[i+m].x/tot+0.5);
    }
    for(int i=0;i<=m+1;i++)
    {
        k[i]=0;
    }
    for(int i=0;i<=n-m;i++)
    {
        k[m+1-cnt[i]]++;
    }
    int sum=0;
    for(int i=0;i<=m+1;i++)
    {
        sum+=k[i];
        cout<<sum<<endl;
    }
}
int main ()
{
    int t;
    scanf("%d",&t);
    while(t--)solve();
}