q

q

q次操作，每次给数组

A

A

A或者

B

B

B

[

l

,

r

]

[l,r]

[l,r]位置加上一个斐波那契数列，问每次操作之后

A

B

AB

AB数组是否相同

f

(

x

)

=

1

+

1

x

+

2

x

2

+

.

.

.

+

f

i

b

i

1

x

i

+

.

.

.

=

i

=

0

f

i

b

i

+

1

x

i

x

f

(

x

)

=

i

=

1

f

i

b

i

x

i

,

x

2

f

(

x

)

=

i

=

2

f

i

b

i

1

x

i

f

(

x

)

x

f

(

x

)

x

2

f

(

x

)

=

1

f

(

x

)

=

1

1

x

x

2

f(x)=1+1x+2x^2+...+fib_{i-1}x^i+...=sum_{i=0}fib_{i+1}x^i\ xf(x)=sum_{i=1}fib_{i}x^i,x^2f(x)=sum_{i=2}fib_{i-1}x^i\ f(x)-xf(x)-x^2f(x)=1\ f(x)=frac 1 {1-x-x^2}

f(x)=1+1x+2x2+...+fibi1xi+...=i=0fibi+1xixf(x)=i=1fibixi,x2f(x)=i=2fibi1xif(x)xf(x)x2f(x)=1f(x)=1xx21

A

,

B

A,B

A,B看做两个多项式

A

(

x

)

=

i

=

1

n

a

i

x

i

B

(

x

)

=

i

=

1

n

b

i

x

i

A(x)=sum_{i=1}^{n}a_ix^i\ B(x)=sum_{i=1}^{n}b_ix^i

A(x)=i=1naixiB(x)=i=1nbixi

A

A

A数组

[

l

,

r

]

[l,r]

[l,r]位置加上一个斐波那契数列就相当于

A

(

x

)

+

=

x

l

f

(

x

)

f

i

b

r

l

+

2

x

r

f

(

x

)

f

i

b

r

l

+

1

x

r

+

1

f

(

x

)

A

(

x

)

+

=

x

l

1

1

x

x

2

f

i

b

r

l

+

2

x

r

1

1

x

x

2

f

i

b

r

l

+

1

x

r

+

1

1

1

x

x

2

A(x)+=x^lf(x)-fib_{r-l+2}x^rf(x)-fib_{r-l+1}x^{r+1}f(x)\ iff A(x)+=x^lfrac 1 {1-x-x^2}-fib_{r-l+2}x^rfrac 1 {1-x-x^2}-fib_{r-l+1}x^{r+1}frac 1 {1-x-x^2}

A(x)+=xlf(x)fibrl+2xrf(x)fibrl+1xr+1f(x)A(x)+=xl1xx21fibrl+2xr1xx21fibrl+1xr+11xx21

(

1

x

x

2

)

(1-x-x^2)

(1xx2)

(

1

x

x

2

)

A

(

x

)

+

=

x

l

f

i

b

r

l

+

2

x

r

f

i

b

r

l

+

1

x

r

+

1

iff (1-x-x^2)A(x)+=x^l-fib_{r-l+2}x^r-fib_{r-l+1}x^{r+1}

(1xx2)A(x)+=xlfibrl+2xrfibrl+1xr+1

O

(

1

)

O(1)

O(1)

(

1

x

x

2

)

A

(

x

)

(1-x-x^2)A(x)

(1xx2)A(x)的实际意义，即构造一个辅助数组

D

D

D

D

i

=

A

i

A

i

1

A

i

2

D_i=A_i-A_{i-1}-A_{i-2}

Di=AiAi1Ai2

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int n,q,mod;
scanf("%d%d%d",&n,&q,&mod);
vector<int>a(n+1),b(n+1);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=n;i>=2;i--)
{
a[i]-=a[i-1]+a[i-2];
a[i]=(a[i]%mod+mod)%mod;
}
for(int i=n;i>=2;i--)
{
b[i]-=b[i-1]+b[i-2];
b[i]=(b[i]%mod+mod)%mod;
}
int cnt=0;
for(int i=1;i<=n;i++)cnt+=(a[i]!=b[i]);
vector<int>fib(n+5);
fib[1]=1%mod;
fib[2]=1%mod;
for(int i=3;i<=n;i++)fib[i]=(fib[i-1]+fib[i-2])%mod;
// printf("cnt=%dn",cnt);
// for(int j=1;j<=n;j++)printf("%d%c",a[j]," n"[j==n]);
// for(int j=1;j<=n;j++)printf("%d%c",b[j]," n"[j==n]);
for(int i=1;i<=q;i++)
{
char c[2];
scanf("%s",c);
int l,r;
scanf("%d%d",&l,&r);
{
if(pos>n)return;
if(id==1)
{
cnt-=(a[pos]!=b[pos]);
a[pos]=(a[pos]%mod+mod)%mod;
cnt+=(a[pos]!=b[pos]);
}
else
{
cnt-=(a[pos]!=b[pos]);
b[pos]=(b[pos]%mod+mod)%mod;
cnt+=(a[pos]!=b[pos]);
}
};
if(c[0]=='A')
{
}
else
{
}
// printf("q=%d cnt=%dn",i,cnt);
// for(int j=1;j<=n;j++)printf("%d%c",a[j]," n"[j==n]);
// for(int j=1;j<=n;j++)printf("%d%c",b[j]," n"[j==n]);
if(cnt==0)printf("YESn");
else printf("NOn");

}
return  0;
}



THE END