Subsequence Count（HDU-6155）

题目描述：

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

思路：

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

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

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

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

(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

(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$）的矩阵即可。

代码

#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;
}

Subsequence Count（HDU-6155）

原文：https://www.cnblogs.com/Heinz/p/10459060.html