Subsequence Count

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 256000/256000 K (Java/Others)

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.

Sample Input

2
4 4
1010
2 1 4
2 2 4
1 2 3
2 1 4
4 4
0000
1 1 2
1 2 3
1 3 4
2 1 4

Sample Output

11
6
8
10

题解：

　　设定dp[i][0/1] 到第i个字符以0/1结尾的子序列方案

　　若s[i] = =1 : dp[i][1] = dp[i-1][0] + dp[i-1][1] + 1;

　　　　　　　　dp[i][0] = dp[i-1][0];

若是s[i] == 0: dp[i][0] = dp[i-1][0] + dp[i-1][1] + 1;

　　　　　　　　dp[i][1] = dp[i-1][1];

　　写成矩阵，用线段树维护一段连续矩阵乘积，有点卡常数

#include<bits/stdc++.h>

using namespace std;

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

typedef unsigned long long ULL;

const long long INF = 1e18+1LL;

const double pi = acos(-1.0);

const int N=5e5+,M=1e6+,inf=;

inline LL read(){

    LL x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const LL mod = 1e9+;

char s[N];

struct Matix {

    LL arr[][];

}E,F,again,EE;

inline Matix mul(Matix a,Matix b) {

    Matix ans;

    memset(ans.arr,,sizeof(ans.arr));

    for(int i = ; i < ; i++) {

        for(int j = ; j < ; j++) {

            for(int k = ; k < ; k++)

                ans.arr[i][j] += a.arr[i][k] * b.arr[k][j],ans.arr[i][j] %= mod;

        }

    }

    return ans;

}

Matix v[N * ],now,facE[N],facF[N];

int lazy[N * ],fi[N * ],se[N * ];

void change(int i) {

    swap(v[i].arr[][],v[i].arr[][]);

    swap(v[i].arr[][],v[i].arr[][]);

    swap(v[i].arr[][],v[i].arr[][]);

    swap(v[i].arr[][],v[i].arr[][]);

    swap(v[i].arr[][],v[i].arr[][]);

    swap(v[i].arr[][],v[i].arr[][]);

}

void push_down(int i,int ll,int rr) {

    if(!lazy[i]) return;

    lazy[ls] ^= ;

    lazy[rs] ^= ;

    change(ls);change(rs);

    lazy[i] ^= ;

}

inline void push_up(int i,int ll,int rr) {

    v[i] = mul(v[ls],v[rs]);

}

void build(int i,int ll,int rr) {

    lazy[i] = ;

    if(ll == rr) {

        if(s[ll] == '') v[i] = E,fi[i] = ,se[i] = ;

        else v[i] = F,fi[i] = ,se[i] = ;

        return ;

    }

    build(ls,ll,mid);

    build(rs,mid+,rr);

    push_up(i,ll,rr);

}

inline void update(int i,int ll,int rr,int x,int y) {

    push_down(i,ll,rr);

    if(ll == x && rr == y) {

        lazy[i] ^= ;

        change(i);

        return ;

    }

    if(y <= mid) update(ls,ll,mid,x,y);

    else if(x > mid) update(rs,mid+,rr,x,y);

    else update(ls,ll,mid,x,mid),update(rs,mid+,rr,mid+,y);

    push_up(i,ll,rr);

}

inline Matix ask(int i,int ll,int rr,int x,int y) {

    push_down(i,ll,rr);

    if(ll == x && rr == y) {

        return v[i];

    }

    if(y <= mid) return ask(ls,ll,mid,x,y);

    else if(x > mid) return ask(rs,mid+,rr,x,y);

    else return mul(ask(ls,ll,mid,x,mid),ask(rs,mid+,rr,mid+,y));

    push_up(i,ll,rr);

}

int main() {

    EE.arr[][] = ,EE.arr[][] = ,EE.arr[][] = ;

    E.arr[][] = ;E.arr[][] = ;E.arr[][] = ;

    E.arr[][] = ;E.arr[][] = ;

    F.arr[][] = ;F.arr[][] = ;F.arr[][] = ;

    F.arr[][] = ;F.arr[][] = ;

    again.arr[][] = ;

    int T;

    T = read();

    while(T--) {

        int n,Q;

        n = read();

        Q = read();

        scanf("%s",s+);

        build(,,n);

        while(Q--) {

            int op,l,r;

            op = read();

            l = read();

            r = read();

            if(op == )

                update(,,n,l,r);

            else {

                now = mul(again,ask(,,n,l,r));

                printf("%lld\n",(now.arr[][]+now.arr[][])%mod);

            }

        }

    }

    return ;

}

先考虑怎么算 s_1, s_2, \ldots, s_ns1,s2,…,sn 的答案。设 dp(i, 0/1)dp(i,0/1) 表示考虑到 s_isi，以 0/10/1 结尾的串的数量。那么 dp(i, 0) =dp(i - 1, 0) + dp(i - 1, 1) + 1dp(i,0)=dp(i−1,0)+dp(i−1,1)+1. 11 也同理。
那么假设在某个区间之前，dp(i, 0/1) = (x, y)dp(i,0/1)=(x,y) 的话，过了这段区间，就会变成 (ax + by + c, dx + ey + f)(ax+by+c,dx+ey+f) 的形式，只要用线段树维护这个线性变化就好了。

巴特西

HDU 6155 Subsequence Count 线段树维护矩阵

Subsequence Count

最新文章

热门文章