[Contest20171006]Subsequence Count

给定一个01串$S_{1\cdots n}$和$Q$个操作。
操作有两种类型：
1、将$[l,r]$区间的数取反（将其中的$0$变成$1$，$1$变成$0$）。
2、询问字符串$S$的子串$S_{l\cdots r}$有多少个不同的子序列。由于答案可能很大，请将答案对$10^9+7$取模。
在数学中，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

先不管修改，看一看怎么DP找出子序列个数

$f_{i,j}(1\leq i\leq n,j\in\{0,1\})$表示从前$i$个数中选，以$j$为结尾的不同子序列个数

#若$S_{i+1}='0'$

我们可以把$S_{i+1}$连接到$f_{i,0}$和$f_{i,1}$的方案后面组成新的方案，或让$S_{i+1}$单独成子序列，则$f_{i+1,0}=f_{i,1}+f_{i,0}+1$

因为$S_{i+1}='0'$，所以$f_{i+1,1}=f_{i,1}$

#若$S_{i+1}='1'$

$f_{i+1,1}=f_{i,1}+f_{i,0}+1$

因为$S_{i+1}='1'$，所以$f_{i+1,0}=f_{i,0}$

这个转移是线性的，为了让之后的区间查询更为方便，我们不妨把它写成矩阵转移的形式

若$S_{i+1}='0'$，$\left(\begin{matrix}f_{i,0}&f_{i,1}&1\end{matrix}\right)\cdot\left(\begin{matrix}1&0&0\\1&1&0\\1&0&1\end{matrix}\right)=\left(\begin{matrix}f_{i+1,0}&f_{i+1,1}&1\end{matrix}\right)$

若$S_{i+1}='1'$，$\left(\begin{matrix}f_{i,0}&f_{i,1}&1\end{matrix}\right)\cdot\left(\begin{matrix}1&1&0\\0&1&0\\0&1&1\end{matrix}\right)=\left(\begin{matrix}f_{i+1,0}&f_{i+1,1}&1\end{matrix}\right)$

有了转移矩阵，我们就可以用线段树求出任意一段区间的答案

下面考虑修改

将某段区间取反实际上就是把线段树中（这个区间的叶节点）的转移矩阵交换并更新相应节点，如果能打lazy tag就最好了

$\left(\begin{matrix}1&0&0\\1&1&0\\1&0&1\end{matrix}\right)\Leftrightarrow\left(\begin{matrix}1&1&0\\0&1&0\\0&1&1\end{matrix}\right)$

这时我们应该yy一个变换$T$使得任一个转移矩阵通过变换$T$变为另一个转移矩阵

因为我们在线段树上统计答案，所以我们要找的变换$T$应该可以支持区间合并，即

$T(A_1)\cdot T(A_2)\cdot\cdots\cdot T(A_n)=T(A_1\cdot A_2\cdot\cdots\cdot A_n)$

也就是说，我们应该用初等变换组成$T$

观察两个矩阵

$\left(\begin{matrix}1&0&0\\1&1&0\\1&0&1\end{matrix}\right)\left(\begin{matrix}1&1&0\\0&1&0\\0&1&1\end{matrix}\right)$

两个矩阵都有一排竖的$1$，我们不妨交换第$1$和第$2$列

$\left(\begin{matrix}1&0&0\\1&1&0\\1&0&1\end{matrix}\right)\Rightarrow\left(\begin{matrix}0&1&0\\1&1&0\\0&1&1\end{matrix}\right)$

看出什么了吗？我们只需要再交换第一第二行就可以让它变成另一个转移矩阵了！

$\left(\begin{matrix}1&0&0\\1&1&0\\1&0&1\end{matrix}\right)\Rightarrow\left(\begin{matrix}0&1&0\\1&1&0\\0&1&1\end{matrix}\right)\Rightarrow\left(\begin{matrix}1&1&0\\0&1&0\\0&1&1\end{matrix}\right)$

所以我们可以写出$T(A)=\left(\begin{matrix}0&1&0\\1&0&0\\0&0&1\end{matrix}\right)\cdot A\cdot\left(\begin{matrix}0&1&0\\1&0&0\\0&0&1\end{matrix}\right)$

那么它的性质能否支持区间合并呢？我们来算一下，

真是令人愉悦~

至此，我们解决了所有问题，总结思路如下：

建一棵线段树，每个节点代表的区间为$[l,r]$，存储$f_{l-1}$到$f_r$的转移矩阵之积

访问节点时，对相应节点进行一次$T$变换

其他按照正常线段树的方法来就行

最后的一点点细节：

开始时，我们给出的矩阵是这样的

如何方便地处理$\left(\begin{matrix}f_{i,0}&f_{i,1}&1\end{matrix}\right)$呢

假设我们从$l$开始DP

若$S_l='0'$，$\left(\begin{matrix}f_{l,0}&f_{l,1}&1\end{matrix}\right)=\left(\begin{matrix}1&0&1\end{matrix}\right)$
若$S_l='1'$，$\left(\begin{matrix}f_{l,0}&f_{l,1}&1\end{matrix}\right)=\left(\begin{matrix}0&1&1\end{matrix}\right)$

这和转移矩阵的第三行完全一致，所以我们可以把转移的式子改写为：

若$S_{i+1}='0'$，$\left(\begin{matrix}?&?&?\\?&?&?\\f_{i,0}&f_{i,1}&1\end{matrix}\right)\cdot\left(\begin{matrix}1&0&0\\1&1&0\\1&0&1\end{matrix}\right)=\left(\begin{matrix}?&?&?\\?&?&?\\f_{i+1,0}&f_{i+1,1}&1\end{matrix}\right)$

若$S_{i+1}='1'$，$\left(\begin{matrix}?&?&?\\?&?&?\\f_{i,0}&f_{i,1}&1\end{matrix}\right)\cdot\left(\begin{matrix}1&1&0\\0&1&0\\0&1&1\end{matrix}\right)=\left(\begin{matrix}?&?&?\\?&?&?\\f_{i+1,0}&f_{i+1,1}&1\end{matrix}\right)$

所以我们查询$[l,r]$时直接查询，答案就是求得矩阵第三行的前两个数之和

真是一道好题w

p.s.这绝对是我有史以来卡时间卡得最紧的一道题

#include<stdio.h>
#define mod 1000000007ll
#define ll long long
struct matrix{
	ll x[3][3];
	matrix(){
		x[0][1]=x[0][2]=x[1][0]=x[1][2]=x[2][0]=x[2][1]=0;
		x[0][0]=x[1][1]=x[2][2]=1;
	}
}ans;
char s[100010];
matrix laz[400010];
int rev[400010];
matrix operator*(matrix a,matrix b){
	matrix c;
	int i,j,k;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			c.x[i][j]=0;
			for(k=0;k<3;k++)c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%mod;
		}
	}
	return c;
}
void pushup(int x){
	laz[x]=laz[x<<1]*laz[x<<1|1];
}
void build(int l,int r,int x){
	if(l==r){
		if(s[l]=='0')
			laz[x].x[1][0]=laz[x].x[2][0]=1;
		else
			laz[x].x[0][1]=laz[x].x[2][1]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	pushup(x);
}
void swap(ll&a,ll&b){a^=b^=a^=b;}
void change(matrix&a){
	swap(a.x[0][0],a.x[0][1]);
	swap(a.x[1][0],a.x[1][1]);
	swap(a.x[2][0],a.x[2][1]);
	swap(a.x[0][0],a.x[1][0]);
	swap(a.x[0][1],a.x[1][1]);
}
void pushdown(int x){
	if(rev[x]){
		rev[x<<1]^=1;
		change(laz[x<<1]);
		rev[x<<1|1]^=1;
		change(laz[x<<1|1]);
		rev[x]=0;
	}
}
void modify(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R){
		rev[x]^=1;
		change(laz[x]);
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if(L<=mid)modify(L,R,l,mid,x<<1);
	if(mid<R)modify(L,R,mid+1,r,x<<1|1);
	pushup(x);
}
matrix query(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R)return laz[x];
	pushdown(x);
	matrix res;
	int mid=(l+r)>>1;
	if(L<=mid)res=res*query(L,R,l,mid,x<<1);
	if(mid<R)res=res*query(L,R,mid+1,r,x<<1|1);
	return res;
}
int main(){
	int n,m,op,l,r;
	scanf("%d%d%s",&n,&m,s+1);
	build(1,n,1);
	while(m--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
			modify(l,r,1,n,1);
		else{
			 ans=query(l,r,1,n,1);
			 printf("%lld\n",(ans.x[2][0]+ans.x[2][1])%mod);
		}
	}
}

巴特西

[Contest20171006]Subsequence Count

最新文章

热门文章