hdu6155

acm hdu

#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define mem0(x) memset(x, 0, sizeof(x))
#define mem1(x) memset(x, -1, sizeof(x))
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define de(x) cout << #x << "=" << x << endl;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = a; i > b; i--)
#define setI freopen("input.txt", "r", stdin);
#define setIO(x) freopen(x".in", "r", stdin);freopen(x".out","w", stdout);
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
//---------------------------------------------------------//
const int N = 2e5 + 5;
const LL MOD = 1e9 + 7;
int n, q;
char str[N];
struct Matrix
{
    LL m[3][3];
    Matrix(){ mem0(m); }
    void init(){ rep(i, 0, 3) rep(j, 0, 3) m[i][j] = (i == j); }
    Matrix operator * (const Matrix& r) const
    {
        Matrix ret;
        rep(i, 0, 3) rep(j, 0, 3)
        {
            ret.m[i][j] = 0;
            rep(k, 0, 3)  ret.m[i][j] += m[i][k] * r.m[k][j];
            ret.m[i][j] %= MOD;
        }
        return ret;
    }
    void print()
    {
        rep(i, 0, 3) rep(j, 0, 3) printf("%lld%c", m[i][j], " \n"[j==2]);
    }
} M0, M1;
struct SegTree
{
    #define lson t << 1, l, mid
    #define rson t << 1 | 1, mid + 1, r
    Matrix tree[N * 4 + 5];
    bool col[N * 4 + 5];
    void pushup(int t)
    {
        tree[t] = tree[t << 1] * tree[t << 1 | 1];
    }
    void flip(Matrix &r)
    {
        swap(r.m[0][0], r.m[0][1]);
        swap(r.m[1][0], r.m[1][1]);
        swap(r.m[2][0], r.m[2][1]);
        swap(r.m[0][0], r.m[1][0]);
        swap(r.m[0][1], r.m[1][1]);
        swap(r.m[0][2], r.m[1][2]);
    }
    void pushdown(int t, int l, int r)
    {
        if (l == r)  return ;
        int m = r - l + 1;
        if (col[t])
        {
            col[t << 1] ^= col[t];
            col[t << 1 | 1] ^= col[t];
            flip(tree[t << 1]);
            flip(tree[t << 1 | 1]);
            col[t] = 0;
        }
    }
    void build(int t, int l, int r)
    {
        col[t] = 0;
        if (l == r)
        {
            tree[t] = (str[l] == '0' ? M0 : M1);
            return ;
        }
        int mid = l + r >> 1;
        build(lson);
        build(rson);
        pushup(t);
    }
    void change(int t, int l, int r, int a, int b)
    {
        if (a == l && b == r)
        {
            col[t] ^= 1;
            flip(tree[t]);
            return ;
        }
        pushdown(t, l, r);
        int mid = l + r >> 1;
        if (b <= mid)  change(lson, a, b);
        else if (a > mid)  change(rson, a, b);
        else
        {
            change(lson, a, mid);
            change(rson, mid + 1, b);
        }
        pushup(t);
    }
    Matrix query(int t, int l, int r, int a, int b)
    {
        if (a == l && b == r)  return tree[t];
        pushdown(t, l, r);
        int mid = l + r >> 1;
        if (b <= mid)  return query(lson, a, b);
        else if (a > mid)  return query(rson, a, b);
        else  return query(lson, a, mid) * query(rson, mid + 1, b);
    }
} T;
void init()
{
    M0.m[0][0] = M0.m[1][0] = M0.m[1][1] = M0.m[2][0] = M0.m[2][2] = 1;
    M1.m[0][0] = M1.m[0][1] = M1.m[1][1] = M1.m[2][1] = M1.m[2][2] = 1;
}
int main()
{
    #ifdef M1saki
        setI;
    #endif
//  ios::sync_with_stdio(false);
    init();
    int Case; scanf("%d", &Case);
    while (Case--)
    {
        scanf("%d%d%s", &n, &q, str + 1);
        T.build(1, 1, n);
        while (q--)
        {
            int op, x, y; scanf("%d%d%d", &op, &x, &y);
            if (op == 1)
                T.change(1, 1, n, x, y);
            else
            {
                Matrix ans = T.query(1, 1, n, x, y);
                printf("%lld\n", (ans.m[2][0] + ans.m[2][1]) % MOD);
            }
        }
    }
    return 0;
}