Codeforces #770 : Div2 F. Fibonacci Additions

この回はフル参加してないので特に感想もないな…。
https://codeforces.com/contest/1634/problem/F

問題

2つの整数列A,Bがある。
クエリとして、いずれかの整数列の部分列に、フィボナッチ数列(1,1,2,3,5....)を足しこむよう指示される。
各クエリのあと、AとBの各要素をMで割った余りが一致するか判定せよ。

解法

以下の2つの補助的な数列を考える。
C[i]=A[i]-B[i]
D[i]=C[i]-C[i-1]-C[i-2]

すべてC及びDが(mod Mで)0であれば、A=Bである。
A[L]....A[R]にフィボナッチ数を足すクエリは、D[L]をインクリメントし、D[R]からF(R-L+1)、D[R+1]からF(R-L+2)を引くのと同値である。
よってクエリ毎にDのうち3要素だけ更新し、全部0か判定すればよい。

int N,Q;
int A[303030],B[303030],C[303030],D[303030],F[303030];
int mo;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&Q,&mo);
	FOR(i,N) scanf("%d",&A[i+1]);
	int NZ=0;
	FOR(i,N) {
		scanf("%d",&B[i+1]);
		C[i+1]=A[i+1]+mo-B[i+1];
		if(C[i+1]>=mo) C[i+1]-=mo;
		D[i+1]=C[i+1];
		if(i) D[i+1]-=C[i];
		if(i-1) (D[i+1]-=C[i-1]);
		while(D[i+1]<0) D[i+1]+=mo;
		if(D[i+1]==0) NZ++;
	}
	
	F[1]=1%mo;
	for(i=2;i<=N+3;i++) {
		F[i]=(F[i-1]+F[i-2]);
		if(F[i]>=mo) F[i]-=mo;
	}
	
	
	while(Q--) {
		char buf[10];
		scanf("%s%d%d",buf,&x,&y);
		if(D[x]==0) NZ--;
		if(y+1<=N && D[y+1]==0) NZ--;
		if(y+2<=N && D[y+2]==0) NZ--;
		if(buf[0]=='A') {
			D[x]+=1;
			D[y+1]+=mo-F[y+1-(x-1)];
			D[y+2]+=mo-F[y+0-(x-1)];
		}
		else {
			D[x]+=mo-1;
			D[y+1]+=F[y+1-(x-1)];
			D[y+2]+=F[y+0-(x-1)];
		}
		if(D[x]>=mo) D[x]-=mo;
		if(D[y+1]>=mo) D[y+1]-=mo;
		if(D[y+2]>=mo) D[y+2]-=mo;
		
		
		if(D[x]==0) NZ++;
		if(y+1<=N && D[y+1]==0) NZ++;
		if(y+2<=N && D[y+2]==0) NZ++;
		
		if(NZ==N) {
			_P("YES\n");
		}
		else {
			_P("NO\n");
		}
	}
	
}

まとめ

差を取ってどうにかするまでは思いつくにせよ、そういう差の取り方はすんなり思い浮かばなかった…。