计数

给定一个长度为 N 的 0,1 数字串,加下来有 Q 个操作。
有两类操作:
1.输入[l,r]将区间内的数字取反。
2.询问[l,r]内的有几中不同的子序列。

N，Q小于1e5

https://www.cnblogs.com/iRedBean/p/7398272.html这篇博客讲的很好。

这道题就是把dp方程化成矩阵运算，然后线段树维护矩阵乘即可。

hdu上卡时间，注意优化常数。。

  1 #include <cstdio>
  2 #include <cstring>
  3 using namespace std;
  4 //#define debug
  5 
  6 typedef long long LL;
  7 #ifdef debug
  8 const LL maxn=10, prime=1e9+7;
  9 #else
 10 const LL maxn=1e5+10, prime=1e9+7;
 11 #endif
 12 const LL mat1[3][3]={{1,0,0},{1,1,0},{1,0,1}};
 13 const LL mat2[3][3]={{1,1,0},{0,1,0},{0,1,1}};
 14 //前面res只开了maxn。。调了好久
 15 LL t, res[maxn*4];
 16 LL n, q, x, L, R;
 17 char s[maxn];
 18 
 19 void swap(LL &a, LL &b){
 20     LL t=a; a=b; b=t;
 21 }
 22 
 23 struct Matrix33{
 24     LL mat[3][3];
 25     //引用避免多个临时变量
 26     //这里不能写成&b，不然右值传不进来！
 27     Matrix33 operator *(Matrix33 b){
 28         Matrix33 m;
 29         for (LL i=0; i<3; ++i) for (LL j=0; j<3; ++j){
 30             m.mat[i][j]=0;
 31             for (LL k=0; k<3; ++k)
 32                 m.mat[i][j]=(m.mat[i][j]+mat[i][k]*b.mat[k][j])%prime;
 33         }
 34         return m;
 35     }
 36     void reserve(){
 37         //能加速
 38         swap(mat[0][0], mat[1][1]); swap(mat[0][1], mat[1][0]);
 39         swap(mat[0][2], mat[1][2]); swap(mat[2][0], mat[2][1]);
 40     }
 41 }seg[maxn*4], unit, ans, dp;
 42 
 43 void build(LL now, LL l, LL r){
 44     //这个必须写在前面！
 45     res[now]=0;
 46     if (l==r){
 47         memcpy(seg[now].mat, s[l-1]=='0'?mat1:mat2, sizeof(mat1));
 48         return;
 49     }
 50     LL mid=(l+r)>>1;
 51     build(now<<1, l, mid); build(now<<1|1, mid+1, r);
 52     seg[now]=seg[now<<1]*seg[now<<1|1];
 53 }
 54 
 55 void pushdown(LL now){
 56     if (res[now]){
 57         res[now<<1]^=1, res[now<<1|1]^=1;
 58         seg[now<<1].reserve();
 59         seg[now<<1|1].reserve();
 60         //忘记清零了！
 61         res[now]=0;
 62     }
 63 }
 64 
 65 void modify(LL now, LL l, LL r){
 66     if (l>=L&&r<=R){
 67         seg[now].reserve();
 68         res[now]^=1;
 69         return;
 70     }
 71     pushdown(now);
 72     LL mid=(l+r)>>1;
 73     if (mid>=L) modify(now<<1, l, mid);
 74     if (mid<R) modify(now<<1|1, mid+1, r);
 75     seg[now]=seg[now<<1]*seg[now<<1|1];
 76 }
 77 
 78 Matrix33 query(LL now, LL l, LL r){
 79     if (l>=L&&r<=R) return seg[now];
 80     pushdown(now);
 81     LL mid=(l+r)>>1;
 82     Matrix33 re=unit;
 83     if (mid>=L) re=re*query(now<<1, l, mid);
 84     if (mid<R) re=re*query(now<<1|1, mid+1, r);
 85     return re;
 86 }
 87 
 88 inline bool isdigit(char c) { return c>47&&c<58?true:false; }
 89 inline LL getuLL(){
 90     char c; LL r=0;
 91     for (c=getchar(); !isdigit(c); c=getchar());
 92     while (isdigit(c)) r=r*10+c-48, c=getchar();
 93     return r;
 94 }
 95 
 96 int main(){
 97     unit.mat[0][0]=unit.mat[1][1]=unit.mat[2][2]=1;
 98     t=getuLL();
 99     for (LL tt=0; tt<t; ++tt){
100         n=getuLL(), q=getuLL();
101         scanf("%s", s);
102         build(1, 1, n);
103         for (LL i=0; i<q; ++i){
104             x=getuLL(), L=getuLL(), R=getuLL();
105             if (x==1) modify(1, 1, n);
106             if (x==2){
107                 memset(dp.mat, 0, sizeof(dp.mat));
108                 dp.mat[0][2]=1;
109                 ans=query(1, 1, n); dp=dp*ans;
110                 printf("%lld
", (dp.mat[0][0]%prime+dp.mat[0][1])%prime);
111             }
112         }
113     }
114     return 0;
115 }