F. Fibonacci Additions

发布时间 2023-08-20 20:32:36作者: 久远寺冇珠

 题意:给两个长度相同的数组,给出q次操作,a操作时对于a中的l与r,l项加上斐波那契的第一项,l+1加第二项,以此类推。b操作把前文中a数组改为b即可。操作完输出yes或no,表示操作后两个数组值在模mod后是否相同。

做法:考虑斐波那契原有的性质,fn=fn-1+fn-2,所以对于a操作,如果n在闭区间[l+1,r]中,设a,b差值数组为c,namo,ci减ci-1减ci-2这个值是不变的,所以我们只需要维护三个变量就好了

那便是 (ci)-(ci-1)-(ci-2),(cr+1)-(cr)-(cr-1),(cr+1)-(cr)-(cr-1)。进一步的说,设di=(ci)-(ci-1)-(ci-2),则让dl,dr+1,dr+2分别加上或减去1,fab[r+1],fab[r]。加和减取决于你定义的c是a减b还是b减a以及a操作中。然后定义cnt变量为非0的数量,每一次看看这三个值有无对cnt造成影响。如果cnt为0就是yes,否则就是no。本题就可以愉快的ac了。感谢阅读

void solve(){
    int n,q,m;cin>>n>>q>>m;
    vector<int>fbi(n+1);
    fbi[1]=1,fbi[2]=1;
    int x=1,y=1;
    for(int i=3;i<=n;i++){
        int temp=y;y=(y+x)%m;x=temp;fbi[i]=y%m;
    }
    vector<int>a(n+1);vector<int>b(n+1);vector<int>c(n+1);vector<int>d(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
        int cnt=0ll;
    for(int i=1;i<=n;i++){
        cin>>b[i];c[i]=(a[i]-b[i])%m;
        if(i==1)d[i]=c[i];
        if(i>=2)d[i]=(c[i]-c[i-1]-c[i-2])%m;
        if(d[i]!=0)cnt++;
    }
    while(q--){
        char c;cin>>c;
        if(c=='A'){
            int l,r;cin>>l>>r;
            int temp=d[l];
            d[l]+=1;d[l]%=m;
            if(d[l]==0)cnt--;
            if(temp==0)cnt++;
            if(r<n){
                temp=d[r+1];
                d[r+1]-=fbi[r-l+1]+fbi[r-l];
                d[r+1]%=m;
                if(d[r+1]==0)cnt--;
                if(temp==0)cnt++;
                if(r<n-1){
                    temp=d[r+2];
                    d[r+2]-=fbi[r-l+1];
                    d[r+2]%=m;
                    if(d[r+2]==0)cnt--;
                    if(temp==0)cnt++;
                }
            }
            if(cnt==0)cout<<"YES\n";
            else cout<<"NO\n";
        }
        else{
            int l,r;cin>>l>>r;
            int temp=d[l];
            d[l]-=1;d[l]%=m;
            if(d[l]==0)cnt--;
            if(temp==0)cnt++;
            if(r<n){
                temp=d[r+1];
                d[r+1]+=fbi[r-l+1]+fbi[r-l];
                d[r+1]%=m;
                if(d[r+1]==0)cnt--;
                if(temp==0)cnt++;
                if(r<n-1){
                    temp=d[r+2];
                    d[r+2]+=fbi[r-l+1];
                    d[r+2]%=m;
                    if(d[r+2]==0)cnt--;
                    if(temp==0)cnt++;
                }
            }
            if(cnt==0)cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
}