hdu_6155 Subsequence Count

题目:

  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].

思路:

  先考虑暴力的dp,设 表示到第 位,结尾为 的方案数。那么转移如下(设 ):
  
  (所有以 结尾的,以 为结尾的,单独的一个
  
  (所有不以 为结尾的)
  显然这个转移是可以矩阵优化的,每次要进行区间的查询,就在线段树上维护每个区间矩阵的乘积。修改就直接翻转矩阵即可。复杂度 。其实每个矩阵的最后一列都是一样的,所以可以优化到 (但是我没这么写)。

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;
const int N=1e5+5,MOD=1e9+7;

const int M1[3][3]={{1,1,0},
                    {0,1,0},
                    {0,1,1}};

struct Matrix{
    int n,m;
    int a[4][4];
    int* operator [] (int x){return a[x];}
    Matrix operator * (Matrix b) const {
        Matrix ans;
        ans.n=n;ans.m=b.m;
        rep(i,1,n)
            rep(j,1,b.m)
                ans[i][j]=0;
        rep(i,1,n)
            rep(k,1,m)
                rep(j,1,b.m)
                    (ans[i][j]+=(ll)a[i][k]*b[k][j]%MOD)%=MOD;
        return ans;
    }
    Matrix flip(){
        Matrix ans;
        ans.n=ans.m=3;
        int f[]={0,2,1,3};
        rep(i,1,3)
            rep(j,1,3){
                int x=f[i],y=f[j];
                ans[x][y]=a[i][j];
            }
        return ans;
    }
};

Matrix seg[N<<2];
bool flag[N<<2];
char s[N];
#define ls (o<<1)
#define rs (o<<1|1)
#define mid (L+R>>1)
#define lson ls,L,mid
#define rson rs,mid+1,R
void build(int o,int L,int R){
    flag[o]=false;
    if(L==R){
        seg[o].n=seg[o].m=3;
        rep(i,1,3)
            rep(j,1,3)
                seg[o][i][j]=M1[i-1][j-1];
        if(s[L]=='0')
            seg[o]=seg[o].flip();
        return;
    }
    build(lson);build(rson);
    seg[o]=seg[ls]*seg[rs];
}
void down(int o){
    if(!flag[o])return;
    seg[ls]=seg[ls].flip();
    seg[rs]=seg[rs].flip();
    flag[ls]^=1;
    flag[rs]^=1;
    flag[o]=0;
}
void upd(int l,int r,int o,int L,int R){
    if(l==L&&r==R){
        seg[o]=seg[o].flip();
        flag[o]^=1;
        return;
    }
    down(o);
    if(r<=mid)upd(l,r,lson);
    else if(l>mid)upd(l,r,rson);
    else upd(l,mid,lson),upd(mid+1,r,rson);
    seg[o]=seg[ls]*seg[rs];
}
Matrix qry(int l,int r,int o,int L,int R){
    if(l==L&&r==R)return seg[o];
    down(o);
    if(r<=mid)return qry(l,r,lson);
    else if(l>mid)return qry(l,r,rson);
    else return qry(l,mid,lson)*qry(mid+1,r,rson);
}

int main(){
    int cas,n,q;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        build(1,1,n);
        while(q--){
            int t,l,r;
            scanf("%d%d%d",&t,&l,&r);
            if(t==1)
                upd(l,r,1,1,n);
            else {
                Matrix m1,m2=qry(l,r,1,1,n);
                m1.n=1;m1.m=3;
                m1[1][1]=m1[1][2]=0;m1[1][3]=1;
                m1=m1*m2;
                int ans=(m1[1][1]+m1[1][2])%MOD;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}