DP式很容易得到,发现是线性递推形式,于是可以矩阵加速。又由于是区间形式,所以用线段树维护。

https://www.cnblogs.com/Miracevin/p/9124511.html

关键在于证明区间操作中,可以直接在打标记的位置翻转矩阵两行两列。

上面网址用代数形式证了一遍,这里考虑从矩阵本身解释。

由线代内容可知,将一个矩阵作初等行变换,相当于将其左乘一个作了相应初等列变换的单位矩阵。同理将一个矩阵作初等列变换,相当于将其又乘一个作了相应初等行变换的单位矩阵。

这里,左乘的矩阵$T=\begin{bmatrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}$,右乘的矩阵$T'$同样也是这个。

我们发现,$T\times T'$就是单位矩阵,也就是说$T$的逆矩阵就是自己。

于是有,$T\times A\times T'\times T\times B\times T'=T\times A\times B\times T'$。

这就说明中间的所有矩乘操作都可以被省略,只留下首尾的$T$和$T'$。

这也就证明了,对区间矩阵积直接做变换是正确的。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (x<<1)
#define rs (ls|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,mod=1e9+;
bool tag[N<<];
int n,Q,T,op,l,r; struct Mat{ int a[][]; }v[N<<];
const Mat D[]={(Mat){,,,,,,,,},(Mat){,,,,,,,,}};
int calc(Mat a){ return (a.a[][]+a.a[][])%mod; } Mat operator *(const Mat &a,const Mat &b){
Mat c; memset(c.a,,sizeof(c.a));
rep(i,,) rep(j,,) rep(k,,)
c.a[i][k]=(c.a[i][k]+1ll*a.a[i][j]*b.a[j][k])%mod;
return c;
} void put(int x){
tag[x]^=;
swap(v[x].a[][],v[x].a[][]);
swap(v[x].a[][],v[x].a[][]);
swap(v[x].a[][],v[x].a[][]);
swap(v[x].a[][],v[x].a[][]);
swap(v[x].a[][],v[x].a[][]);
swap(v[x].a[][],v[x].a[][]);
} void push(int x){ if (tag[x]) put(ls),put(rs),tag[x]=; } void build(int x,int L,int R){
tag[x]=;
if (L==R){ char t; scanf(" %c",&t); v[x]=D[t-'']; return; }
int mid=(L+R)>>; build(lson); build(rson); v[x]=v[ls]*v[rs];
} void mdf(int x,int L,int R,int l,int r){
if (L==l && r==R){ put(x); return; }
int mid=(L+R)>>; push(x);
if (r<=mid) mdf(lson,l,r);
else if (l>mid) mdf(rson,l,r);
else mdf(lson,l,mid),mdf(rson,mid+,r);
v[x]=v[ls]*v[rs];
} Mat que(int x,int L,int R,int l,int r){
if (L==l && r==R) return v[x];
int mid=(L+R)>>; push(x);
if (r<=mid) return que(lson,l,r);
else if (l>mid) return que(rson,l,r);
else return que(lson,l,mid)*que(rson,mid+,r);
} int main(){
freopen("hdu6155.in","r",stdin);
freopen("hdu6155.out","w",stdout);
for (scanf("%d",&T); T--; ){
scanf("%d%d",&n,&Q); build(,,n);
while (Q--){
scanf("%d%d%d",&op,&l,&r);
if (op==) mdf(,,n,l,r); else printf("%d\n",calc(que(,,n,l,r)));
}
}
return ;
}
05-11 22:12
查看更多