Subsequence Count

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6155
思路：
考虑构造dp
dp[i][j]表示前i个，以j为结尾的不同子序列有多少个。
如果第i个是1，那么
dp[i][1]=dp[i-1][1]+dp[i-1][0]+1,
dp[i][0]=dp[i-1][0]
如果第i个是0，那么
dp[i][1]=dp[i-1][1]
dp[i][0]=dp[i-1][1]+dp[i-1][0]
怎么去想？第i个为1，就把前面i-1个得到的序列都在末尾加上s[i]，那么会导致，没有1这个单独的序列了，(原来的1变为了1,1)那么+1即补上。
这是一个递推式子，那么我们自然可以写出转移矩阵

第i个是1：
1 0 0 
1 1 0 
1 0 1
第i个是0：
1 1 0
0 1 0
0 1 1         

然后关于修改查询用线段树优化，维护矩阵
但你可能会问flip不是对矩阵的操作吗？那怎么区间修改呢。很容易验证，就这道题来讲，由于两个矩阵之间相差的是1，2行做一次初等行变换，1，2列做一次初等列变换，如果对一个区间做flip操作，只需要对这个区间之前得到的结果矩阵，做同样的初等行列变换即可。
证：设初等矩阵为p1,2。对矩阵做初等行变换就是左乘初等矩阵，对矩阵做初等列变换就是右乘初等矩阵，如果原来矩阵乘法中，有BA/AB，那么其中间的初等矩阵在做了flip操作后也不会消失，如果是AA/BB，那么其中间的初等矩阵由于会消掉，因此也不会发生改变，所以结论就是矩阵与矩阵间不会产生新的矩阵，flip后只会在两端同乘初等矩阵，此结论仅限于本题，其他题可以类似的去考虑。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1e5+7;
const int mod = 1e9+7;
const int mSize = 3;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

struct Matrix
{
    long long v[mSize][mSize];
    friend Matrix operator* (const Matrix& a, const Matrix& b)
    {
        Matrix c;
        for (int i = 0; i < mSize; i++)
            for (int j = 0; j < mSize; j++)
            {
                c.v[i][j] = 0;
                for (int k = 0; k < mSize; k++)
                    c.v[i][j] += a.v[i][k] * b.v[k][j] % mod;
                c.v[i][j] %= mod;
            }
        return c;
    }
};

const Matrix m[2] = {{1, 0, 0, 1, 1, 0, 1, 0, 1},{1, 1, 0, 0, 1, 0, 0, 1, 1}};

char s[maxn];
Matrix data[maxn<<2];
bool flip[maxn<<2];



inline void mat_build(int o, int l, int r)
{
    if(l == r)
        data[o] = m[s[l] - '0'];
    else{
        int mid = (l + r) >> 1;
        mat_build(o << 1 , l, mid);
        mat_build(o << 1 | 1, mid+1, r);
        data[o] = data[o << 1]*data[o << 1 | 1];
    }
    flip[o] = 0;
}


inline void doFlip(Matrix& mat)
{
    swap(mat.v[0][0], mat.v[0][1]);
    swap(mat.v[1][0], mat.v[1][1]);
    swap(mat.v[2][0], mat.v[2][1]);    
    swap(mat.v[0][0], mat.v[1][0]);
    swap(mat.v[0][1], mat.v[1][1]);
    swap(mat.v[0][2], mat.v[1][2]);
}


inline void pushdown(int o)
{
    if(flip[o])
    {
        flip[o << 1] ^= flip[o];
        flip[o << 1 | 1] ^= flip[o];
        doFlip(data[o << 1]);
        doFlip(data[o << 1 | 1]);
        flip[o] = 0;
    }
}

inline void mat_flip(int o, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
    {
        flip[o] ^= 1;
        doFlip(data[o]);
        return ;
    }
    if(qr < l || ql > r)
    {
        return ;
    }
    int mid = (r + l) >> 1;
    pushdown(o);
    mat_flip(o << 1, l, mid, ql, qr);
    mat_flip(o << 1 | 1, mid+1, r, ql, qr);
    data[o] = data[o << 1]*data[o << 1 | 1];
}


inline Matrix mat_query(int o, int l, int r, int ql, int qr)
{    
    if(ql <= l && r <= qr)
    {
        return data[o];
    }
    if(qr < l || ql > r)
    {
        return {1, 0, 0, 0, 1, 0, 0, 0, 1};
    }
    int mid = (r + l) >> 1;
    pushdown(o);
    return mat_query(o << 1, l, mid, ql, qr) * mat_query(o << 1 | 1, mid+1, r, ql, qr);
}

signed main()
{
    int t;
    scanf("%lld",&t);
    while(t--)
    {
        int n, q;
        scanf("%lld%lld",&n,&q);
        scanf("%s", s + 1);
        mat_build(1, 1, n);
        while(q--)
        {
            int op, l, r;
            scanf("%lld%lld%lld",&op,&l,&r);
            if(op == 1){
                mat_flip(1, 1, n, l, r);
            }
            else{
                Matrix mat = mat_query(1, 1, n, l, r);
                printf("%lld\n",(mat.v[2][0]+mat.v[2][1])%mod);
            }
        }
    }
    return 0;
}