Subsequence Count
题目链接
ccpc网络赛1006
题意是给一个01字符串，然后有2种操作，
1、把l到r这个区间的字符翻转，
2、查询l到r这个区间有多少个不同的子序列，（注意是子序列，可不连续），对1e9+7取模
这个题目在比赛的时候过的人很少
其实对于第二种操作，我们容易得到一个dp[i][0/1]代表前i个字符以0/1结尾的不同子序列有多少个，容易得到方程
if(s[i] == 0)dp[i][0] =dp[i-1][0] + dp[i-1][1] + 1 S[i] == 1同理，然后就是转化区间上的问题，容易想到用一些数据结构来维护，比如线段树，但是用线段树的话必须把这个递推的方程转化为一个可以区间合并的问题。我们知道dp转移有时候可以变为乘上一个矩阵，而且矩阵是满足结合律的，也就是说可以用来区间合并。
当S[i] 为1时，我们可以构造出一个矩阵A，S[i]为0时同理，可以构造出矩阵B
然后我们就可以用线段树来维护一个区间的矩阵的积，
在修改的时候，我们要把某个区间的A矩阵变为B，B矩阵变为A。我们可以对于一个节点可以记录一段区间翻转和未翻转的矩阵积，当某一个区间需要被翻转的时候，把未翻转矩阵和翻转矩阵交换一下即可。因为有Push_up的存在，保证了节点里矩阵是正确的。
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<time.h>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<iostream>
#include<stdlib.h>
using namespace std;
#define LONG long long
const LONG INF=0x3f3f3f3f;
const LONG MOD=1e9+7;
const double PI=acos(-1.0);
#define clrI(x) memset(x,-1,sizeof(x))
#define clr0(x) memset(x,0,sizeof x)
#define clr1(x) memset(x,INF,sizeof x)
#define clr2(x) memset(x,-INF,sizeof x)
#define EPS 1e-10
#define lson l , mid , rt<< 1
#define rson mid + 1 ,r , (rt<<1)|1
#define root 1, n , 1
const int MAXN = 1e5 +100 ;
struct Matr
{LONG matr[3][3] ;void Init(){clr0(matr) ;}
};
Matr x ,y ;
struct Tree
{Matr Real ;Matr Temp ;
} tree[MAXN<<2] ;
int lazy [MAXN<<2] ;
char S[100100] ;
Matr Multi(Matr a , Matr b)
{Matr ret ;ret.Init() ;for(int i = 0;i < 3 ; ++i)for(int j = 0 ;j< 2 ; ++ j)for(int k=0;k< 3; ++k)ret.matr[i][j] = ( ret.matr[i][j] + a.matr[i][k] * b.matr[k][j] ) %MOD ;ret.matr[2][2]= 1;return ret;
}
void Push_up(int rt )
{tree[rt].Real = Multi(tree[rt<<1].Real , tree[rt<<1|1].Real) ;tree[rt].Temp = Multi(tree[rt<<1].Temp , tree[rt<<1|1].Temp ) ;
}
void Build(int l , int r , int rt)
{lazy[rt] = 0;if(l == r ){if(S[l] == '0'){tree[rt].Real = y ;tree[rt].Temp = x ;}else{tree[rt].Real = x ;tree[rt].Temp = y ;}return ;}int mid = (l + r ) /2 ;Build(lson ) ;Build (rson ) ;Push_up(rt) ;
}
void Push_down(int rt )
{if(lazy[rt]){Matr tmp = tree[rt<<1].Real ;tree[rt<<1].Real = tree[rt<<1].Temp ;tree[rt<<1].Temp = tmp ;tmp = tree[rt<<1|1 ].Real ;tree[rt<<1|1].Real = tree[rt<<1|1].Temp ;tree[rt<<1|1].Temp = tmp ;lazy[rt<<1] ^= 1 ;lazy[rt<<1|1] ^= 1;lazy[rt] = 0 ;}
}
void Update(int L ,int R , int l, int r ,int rt )
{if(L <= l &&r <= R){lazy[rt] ^= 1;Matr tmp = tree[rt].Real ;tree[rt].Real = tree[rt].Temp ;tree[rt].Temp = tmp ;return ;}Push_down(rt) ;int mid = (l + r) / 2;if(L <= mid)Update(L, R , l, mid , rt<<1 ) ;if(R > mid )Update(L,R , mid + 1 , r , rt<<1|1) ;Push_up(rt) ;}
Matr Que(int L ,int R ,int l , int r ,int rt )
{if(L <= l &&r <= R ){return tree[rt].Real ;}Push_down(rt) ;int mid = (l +r) / 2;Matr res ;res.Init() ;res.matr[0][0] =1 , res.matr[2][2] = 1 , res.matr[1][1] = 1;if(L <=mid )res = Multi( res ,Que(L , R , lson ) ) ;if(R > mid)res = Multi(res , Que(L ,R ,rson ) ) ;return res ;
}
int main()
{int T ;cin >>T ;x.Init() ;y.matr[0][0] = 1 ,y.matr[1][0] = 1,y.matr[2][0] = 1 ,y.matr[0][1] = 0,y.matr[1][1] = 1 ,y.matr[2][1] = 0,y.matr[0][2] = 0 ,y.matr[1][2] = 0, y.matr[2][2] = 1;x.matr[0][0] = 1 ,x.matr[1][0] = 0,x.matr[2][0] = 0 ,x.matr[0][1] = 1,x.matr[1][1] = 1 ,x.matr[2][1] = 1,x.matr[0][2] = 0 ,x.matr[1][2] = 0, x.matr[2][2] = 1;int n , Q ;while(T --){scanf("%d%d",&n,&Q) ;scanf("%s",S+1) ;Build( root ) ;while(Q -- ){int op ;scanf("%d",&op) ;int l, r ;if(op == 1){scanf("%d%d",&l,&r) ;Update(l ,r ,root ) ;}else{scanf("%d%d",&l , &r) ;Matr res ;res = Que(l , r ,root ) ;printf("%lld\n",(res.matr[2][0] + res.matr[2][1] ) % MOD ) ;}}}return 0 ;
}
