Problem Description
Given a binary string S[1,...,N] (i.e. a sequence of 0's and 1's), and Q queries on the string. There are two types of queries: 1. Flipping the bits (i.e., changing all 1 to 0 and 0 to 1) between l and r (inclusive). 2. Counting the number of distinct subsequences in the substring S[l,...,r].
Input
The first line contains an integer T, denoting the number of the test cases. For each test, the first line contains two integers N and Q. The second line contains the string S. Then Q lines follow, each with three integers type, l and r, denoting the queries. 1≤T≤5 1≤N,Q≤105 S[i]∈{0,1},∀1≤i≤N type∈{1,2} 1≤l≤r≤N
Output
For each query of type 2, output the answer mod (109+7) in one line.
首先考虑怎么求一个01串有多少种不同的子序列
dp[i][0]表示考虑到第i位时以0结尾的不同的子序列个数
dp[i][1]表示考虑到第i位时以1结尾的不同的子序列个数
若第i+1位为1，则有：
以01为结尾的子序列个数为dp[i][0]
以11为结尾的子序列个数为dp[i][1]
只有一个1的子序列个数为1
以0为结尾的子序列个数为dp[i][0]
以上4种情况统计了考虑到i+1处时所有的子序列
于是有 dp[i+1][1]=dp[i][0]+dp[i][1]+1
dp[i+1][0]=dp[i][0]
(1 1 0
（dp[i][0],dp[i][1],1）* 0 1 0 =(dp[i+1][0],dp[i+1][1],1)
0 1 1)
记为A矩阵。
若i+1位为0同理有：
dp[i+1][1]=dp[i][0]
dp[i+1][0]=dp[i][0]+dp[i][1]+1
对应矩阵为（记为B矩阵）
1 0 0
1 1 0
1 0 1
其次考虑优化的问题。将以上的两种转移视为矩阵，用线段树维护矩阵的乘积即可。
对于将所有0换成1,1换成0的操作而言，等价于将所有A矩阵换成B，B换成A,而A和B通过交换1,2行及1,2列可互相转换，或者说，乘以初等矩阵Fs,t ,该矩阵的逆为自身。（记其为F）
0 1 0
1 0 0
0 0 1
于是有FAFFAF……FBF……=FAAB……F，或者说，将大量0换成1,1换成0的时候只需要在乘积最外面进行一次交换1,2行与1,2列的操作。
然而。。仍然TLE..估计是被卡了常数。心塞。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int N,Q;
const long long int mo=1e9+
7;
char s[
5010];
int lazy[
5050<<
2];
struct Matrix{
int n,m;
long long a[
3][
3];
Matrix (){clear();}
void clear(){
n=m=
3;
memset(a,0,
sizeof(a));
}
Matrix operator *(
const Matrix &b)
const{
Matrix tmp;
for (
int i=
0;i<n;++
i)
for (
int j=
0;j<b.m;++
j)
for (
int k=
0;k<m;++
k)
tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*b.a[k][j])%
mo;
return tmp;
}
};
Matrix A0,A1,E;
Matrix cnt[5050<<
2];
inline void init()
{
A0.a[0][
0]=
1,A0.a[
0][
1]=
0,A0.a[
0][
2]=
0;
A0.a[1][
0]=
1,A0.a[
1][
1]=
1,A0.a[
1][
2]=
0;
A0.a[2][
0]=
1,A0.a[
2][
1]=
0,A0.a[
2][
2]=
1;
A1.a[0][
0]=
1,A1.a[
0][
1]=
1,A1.a[
0][
2]=
0;
A1.a[1][
0]=
0,A1.a[
1][
1]=
1,A1.a[
1][
2]=
0;
A1.a[2][
0]=
0,A1.a[
2][
1]=
1,A1.a[
2][
2]=
1;
E.a[0][
0]=
1,E.a[
0][
1]=
0,E.a[
0][
2]=
0;
E.a[1][
0]=
0,E.a[
1][
1]=
1,E.a[
1][
2]=
0;
E.a[2][
0]=
0,E.a[
2][
1]=
0,E.a[
2][
2]=
1;
}
inline void Pushup(
int rt)
{
cnt[rt]=cnt[rt<<
1]*cnt[rt<<
1|
1];
}
inline void build(
int l,
int r,
int rt)
{
if(l==
r)
{
if(s[l-
1]-
'0'==
0)
{
cnt[rt]=
A0;
}
else cnt[rt]=
A1;
return;
}
int m=(l+r)>>
1;
build(lson);
build(rson);
Pushup(rt);
}
inline void change(Matrix &
X)
{
swap(X.a[0][
0],X.a[
1][
1]);
swap(X.a[0][
1],X.a[
1][
0]);
swap(X.a[2][
0],X.a[
2][
1]);
}
inline void pushdown(
int rt)
{
if(lazy[rt])
{
change(cnt[rt<<
1]);
change(cnt[rt<<
1|
1]);
lazy[rt<<
1]^=
1;
lazy[rt<<
1|
1]^=
1;
lazy[rt]=
0;
}
}
inline void update(
int a,
int b,
int l,
int r,
int rt)
{
if(l>=a&&r<=
b)
{
change(cnt[rt]);
lazy[rt]^=
1;
return;
}
pushdown(rt);
int m=(l+r)>>
1;
if(a<=
m) update(a,b,lson);
if(b>
m) update(a,b,rson);
Pushup(rt);
}
inline void Input()
{
scanf("%d%d",&N,&
Q);
scanf("%s",s);
}
inline Matrix query(int a,
int b,
int l,
int r,
int rt)
{
if(l>=a&&r<=b)
return cnt[rt];
pushdown(rt);
Matrix t1=E,t2=
E;
int m=(r+l)>>
1;
if(a<=m) t1=
query(a,b,lson);
if(b>m) t2=
query(a,b,rson);
return t1*
t2;
}
int main()
{
//freopen("in.txt","r",stdin);
int T,type,l,r;
scanf("%d",&
T);
init();
rep(t,1,T)
{
Input();
build(1,N,
1);
rep(i,1,Q)
{
scanf("%d%d%d",&type,&l,&
r);
if(type==
1)
{
update(l,r,1,N,
1);
// rep(j,1,2*N) printf("i=%d dp%d=%lld\n",i,j,(cnt[j].a[2][0]+cnt[j].a[2][1])%mo);
}
else
{
Matrix tmp;
tmp=query(l,r,
1,N,
1);
printf("%lld\n",(tmp.a[
2][
0]+tmp.a[
2][
1])%
mo);
}
}
}
return 0;
}
代码如下：
