CF1634 F. Fibonacci Additions
题意：
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+...+fibi−1xi+...=i=0∑fibi+1xixf(x)=i=1∑fibixi,x2f(x)=i=2∑fibi−1xif(x)−xf(x)−x2f(x)=1f(x)=1−x−x21
如果把
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=1∑naixiB(x)=i=1∑nbixi
那么在
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)−fibr−l+2xrf(x)−fibr−l+1xr+1f(x)⟺A(x)+=xl1−x−x21−fibr−l+2xr1−x−x21−fibr−l+1xr+11−x−x21
两边同乘
(
1
−
x
−
x
2
)
(1-x-x^2)
(1−x−x2)
⟺
(
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}
⟺(1−x−x2)A(x)+=xl−fibr−l+2xr−fibr−l+1xr+1
每次修改复杂度就降为
O
(
1
)
O(1)
O(1)
然后考虑
(
1
−
x
−
x
2
)
A
(
x
)
(1-x-x^2)A(x)
(1−x−x2)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=Ai−Ai−1−Ai−2
#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);
auto add=[&](int id,int pos,int add)
{
// printf("id=%d pos=%d add=%dn",id,pos,add);
if(pos>n)return;
if(id==1)
{
cnt-=(a[pos]!=b[pos]);
a[pos]+=add;
a[pos]=(a[pos]%mod+mod)%mod;
cnt+=(a[pos]!=b[pos]);
}
else
{
cnt-=(a[pos]!=b[pos]);
b[pos]+=add;
b[pos]=(b[pos]%mod+mod)%mod;
cnt+=(a[pos]!=b[pos]);
}
};
if(c[0]=='A')
{
add(1,l,1);
add(1,r+1,-fib[r-l+2]);
add(1,r+2,-fib[r-l+1]);
}
else
{
add(2,l,1);
add(2,r+1,-fib[r-l+2]);
add(2,r+2,-fib[r-l+1]);
}
// 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;
}