首页 > 代码库 > hihocode #1388 : Periodic Signal NTT

hihocode #1388 : Periodic Signal NTT

2024-10-15 05:06:39   216人阅读

#1388 : Periodic Signal

 

描述

Profess X is an expert in signal processing. He has a device which can send a particular 1 second signal repeatedly. The signal is A0 ... An-1 under n Hz sampling.

One day, the device fell on the ground accidentally. Profess X wanted to check whether the device can still work properly. So he ran another n Hz sampling to the fallen device and got B0 ... Bn-1.

To compare two periodic signals, Profess X define the DIFFERENCE of signal A and B as follow:
技术分享
You may assume that two signals are the same if their DIFFERENCE is small enough. 
Profess X is too busy to calculate this value. So the calculation is on you.

输入

The first line contains a single integer T, indicating the number of test cases.

In each test case, the first line contains an integer n. The second line contains n integers, A0 ... An-1. The third line contains n integers, B0 ... Bn-1.

T≤40 including several small test cases and no more than 4 large test cases.

For small test cases, 0<n≤6⋅103.

For large test cases, 0<n≤6⋅104.

For all test cases, 0≤Ai,Bi<220.

输出

For each test case, print the answer in a single line.

样例输入
293 0 1 4 1 5 9 2 65 3 5 8 9 7 9 3 251 2 3 4 52 3 4 5 1
样例输出
800
EmacsNormalVim

 

 题解：
　　化简式子
　　也就是求  
　　技术分享

后面这个只需将B数组倒置，进行卷积，出来就是一段连续的位置是k = 0……n-1,所有情况

　　代码来自huyifan

#include <iostream>#include<cstring>#include<cstdio>using namespace std;#define MAXN 300000typedef long long LL;const long long P=50000000001507329LL;const int G=3;LL mul(LL x,LL y){    return (x*y-(LL)(x/(long double)P*y+1e-3)*P+P)%P;}LL qpow(LL x,LL k,LL p){    LL ret=1;    while(k){        if(k&1) ret=mul(ret,x);        k>>=1;        x=mul(x,x);    }    return ret;}LL wn[25];void getwn(){    for(int i=1; i<=18; ++i){        int t=1<<i;        wn[i]=qpow(G,(P-1)/t,P);    }}int len;void NTT(LL y[],int op){    for(int i=1,j=len>>1,k; i<len-1; ++i){        if(i<j) swap(y[i],y[j]);        k=len>>1;        while(j>=k){            j-=k;            k>>=1;        }        if(j<k) j+=k;    }    int id=0;    for(int h=2; h<=len; h<<=1) {        ++id;        for(int i=0; i<len; i+=h){            LL w=1;            for(int j=i; j<i+(h>>1); ++j){                LL u=y[j],t=mul(y[j+h/2],w);                y[j]=u+t;                if(y[j]>=P) y[j]-=P;                y[j+h/2]=u-t+P;                if(y[j+h/2]>=P) y[j+h/2]-=P;                w=mul(w,wn[id]);            }        }    }    if(op==-1){        for(int i=1; i<len/2; ++i) swap(y[i],y[len-i]);        LL inv=qpow(len,P-2,P);        for(int i=0; i<len; ++i) y[i]=mul(y[i],inv);    }}void Convolution(LL A[],LL B[],int n){    for(len=1; len<(n<<1); len<<=1);    for(int i=n; i<len; ++i){        A[i]=B[i]=0;    }    NTT(A,1); NTT(B,1);    for(int i=0; i<len; ++i){        A[i]=mul(A[i],B[i]);    }    NTT(A,-1);}int t,nn,m;LL a[MAXN],b[MAXN];LL ans,MAX;int main(){    getwn();    scanf("%d",&t);    while(t--)    {        MAX=0;        ans=0;        scanf("%d",&nn);        for(int i=0;i<nn;i++)        {            scanf("%lld",&a[i]);            ans+=a[i]*a[i];        }        for(int i=0;i<nn;i++)        {            scanf("%lld",&b[nn - i - 1]);            ans+=b[nn - i - 1]*b[nn - i - 1];        }        for(int i=0;i<nn;i++)        {            a[i+nn]=a[i];            b[i+nn]=0;        }        Convolution(a,b,2*nn);        for(int i=nn;i<2*nn;i++)        {            MAX=max(MAX,a[i]);        }        printf("%lld\n",ans-2*MAX);    }    return 0;}

 

hihocode #1388 : Periodic Signal NTT


联系
我们