HeinzHuang

Eudaimonia

0%

Subsequence Count（HDU-6155）

Posted on Edited on In

题目描述：

给出一个长度为n的01串S，有Q个操作：
1. 翻转区间\([l,r]\)（0变1,1变0）
2. 求区间\([l,r]\)有多少不同的子串

思路：

看到这题：区间修改，区间询问，不难想到线段树，不过如何快速DP转移？

首先先考虑原本暴力DP的方法，\(dp[x][flag]\)为前\(x\)个数中以\(1\)或\(0\)结尾的子串有多少个。那么便有以下递推关系：

若在第i位上的数字是f,那么 

1
2
3
dp[i][f]=dp[i-1][0]+dp[i-1][1]+1

dp[i][!f]=dp[i-1][!f]
可以把关系式看成三部分：是否要加上一位的dp[0]，是否要加上一位的dp[1]，以及是否要加1.

这样就可以用矩阵乘法转移了

若加入一个1，那么

\(Matrix1=\)
1,1,0
0,1,0
0,1,1

1
(dp[i][0],dp[i][1],1)*Matrix1=(dp[i+1][0],dp[i+1][1],1)

若加入一个0，那么

\(Matrix0=\)
1,0,0
1,1,0
1,0,1

1
(dp[i][0],dp[i][1],1)*Matrix0=(dp[i+1][0],dp[i+1][1],1)
那么最终的答案应当就是(0,0,1)乘上若干个\(Matrix1\)和\(Matrix0\).那么线段树预处理的便是区间的\(Matrix0\)或\(Matrix1\)的乘积了

最后需要的便是\(0\)变\(1\)，\(1\)变\(0\)的操作了。这个不难，一个懒惰标记进行区间维护，每次把一个对于\(1\)（或\(0\)）的矩阵变成\(0\)（或\(1\)）的矩阵即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(i,l,r) for(int i=(int)l;i<=(int)r;i++)
#define DOR(i,r,l) for(int i=(int)r;i>=(int)l;i--)
#define loop(i,n) for(int i=0;i<n;i++)
#define pf printf
#define sf scanf
#define mms(a,x) memset(a,x,sizeof a)
#define ll long long
using namespace std;
const int N=1e5+5,P=1e9+7;
int n,q;
char str[N];
int type,l,r;
struct Matrix{//矩阵 
	int n,m;
	int num[3][3];
	void clear(){mms(num,0);}
	void init(){mms(num,0);loop(i,n)num[i][i]=1;}
	void make_sz(int N,int M){n=N,m=M;}
	void Print(){loop(i,n)loop(j,m)pf("%d%c",num[i][j],j==m-1?'\n':' ');puts("");}
	void flip(){
		swap(num[0][0],num[1][1]);
		swap(num[0][1],num[1][0]);
		swap(num[2][0],num[2][1]);
	}
	Matrix operator *(const Matrix &A){
		Matrix ans;
		ans.make_sz(n,A.m);
		ans.clear();
		loop(i,A.n)loop(j,A.m)
			loop(k,m)ans.num[i][j]=(ans.num[i][j]+1ll*num[i][k]*A.num[k][j])%P;
		return ans;
	}
}S;
Matrix M0={//加入一个0时要乘的矩阵 
	3,3,
	1,0,0,
	1,1,0,
	1,0,1,
};
Matrix M1={//加入一个1时要乘的矩阵 
	3,3,
	1,1,0,
	0,1,0,
	0,1,1,
};
struct YD_Tree{
	#define ls p<<1
	#define rs p<<1|1
	int n,m;
	bool lazy[N<<2];
	Matrix t[N<<2];
	void down(int p){//向下更新需要"翻转"的区间 
		if(!lazy[p])return;
		lazy[ls]^=1,lazy[rs]^=1;
		t[ls].flip(),t[rs].flip();
		lazy[p]=0;
	}
	void up(int p){//一个大区间的矩阵是左右两个矩阵的乘积 
		t[p]=t[ls]*t[rs];
	}
	void build(int p,int l,int r){
		lazy[p]=0;
		if(l==r){
			if(str[l]=='1')t[p]=M1;
			else t[p]=M0;
			return;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		up(p);
	}
	void update(int p,int L,int R,int l,int r){
		if(L<=l&&r<=R){
			lazy[p]^=1;//修改懒惰标记，注意是异或，不是直接等于1 
			t[p].flip();
			return;
		}
		down(p);
		int mid=(l+r)>>1;
		if(mid<R)update(rs,L,R,mid+1,r);
		if(mid>=L)update(ls,L,R,l,mid);
		up(p);
	}
	Matrix Query(int p,int L,int R,int l,int r){//区间询问 
		if(L<=l&&r<=R)return t[p];
		down(p);
		int mid=(l+r)>>1;
		if(R<=mid)return Query(ls,L,R,l,mid);
		else if(L>mid)return Query(rs,L,R,mid+1,r);
		else return Query(ls,L,R,l,mid)*Query(rs,L,R,mid+1,r);
	}
}Tr;
int main(){
	S.make_sz(1,3);
	S.num[0][0]=0,S.num[0][1]=0,S.num[0][2]=1;//起始矩阵 
	int T;
	sf("%d",&T);
	while(T--){
		sf("%d%d",&n,&q);
		sf("%s",str+1);
		Tr.build(1,1,n);
		while(q--){
			sf("%d%d%d",&type,&l,&r);
			if(type==1)Tr.update(1,l,r,1,n);
			else {
				Matrix ret=S*Tr.Query(1,l,r,1,n); 
				pf("%d\n",(ret.num[0][0]+ret.num[0][1])%P);//注意不要把最后一位的常量加上 
			}
		}
	}
	return 0;
}