居然在考场上把这道题打出来了觉得自己也是有点吊啊（虽然后面就没时间做其他题了囧而且还被卡常数了。。。）

题解自己写了一份TEX的就直接放上来吧。。。。

好啦，在谈点什么别的

什么？你在bz上TLE了？注意一下你的矩阵乘法，这个程序的大部分时间几乎都是跑矩阵乘法的，我是从900000次到600000次在到300000次最后预处理那些2的次幂才过的。把OJ卡了好久真是对不起啊QAQ

CODE：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 #define maxn 300010  7 #define mod 1000000007  8 typedef long long ll;  9 inline ll power(ll x,int y) { 10     ll ans=1; 11     for (;y;y>>=1) { 12     if (y&1) (ans*=x)%=mod; 13     (x*=x)%=mod; 14     } 15     return ans; 16 } 17 struct node{ 18     int l,r,ch[3][3],lz[2],s[2][3]; 19     inline void print() { 20     printf("%d %d\n",l,r); 21     for (int i=0;i<3;i++,puts(""))  22         for (int j=0;j<3;j++) printf("%d ",ch[i][j]); 23     for (int i=0;i<2;i++,puts("")) 24         for (int j=0;j<3;j++) printf("%d ",s[i][j]); 25     printf("%d %d\n",lz[0],lz[1]); 26     } 27 }t[maxn*8]; 28 #define lc (x<<1) 29 #define rc (lc^1) 30 #define mid ((l+r)>>1) 31 inline void update(int x){ 32     for (int i=0;i<3;i++)  33     for (int j=0;j<3;j++) t[x].ch[i][j]=(t[lc].ch[i][j]+t[rc].ch[i][j])%mod; 34     for (int i=0;i<2;i++)  35     for(int j=0;j<3;j++) t[x].s[i][j]=(t[lc].s[i][j]+t[rc].s[i][j])%mod; 36 } 37 int a,b,inv; 38 inline void add(int x,int l){ 39     for (int i=0;i<2;i++) t[x].s[l][i]=t[x].s[l][i+1]; 40     t[x].s[l][2]=(t[x].s[l][1]*1ll+t[x].s[l][0]*1ll*a%mod+b*1ll*(t[x].r-t[x].l+1)%mod)%mod; 41     if (l==0) { 42     for (int i=0;i<2;i++)  43         for (int j=0;j<3;j++) t[x].ch[i][j]=t[x].ch[i+1][j]; 44     for (int i=0;i<3;i++)  45         t[x].ch[2][i]=(t[x].ch[1][i]*1ll+t[x].ch[0][i]*1ll*a%mod+b*1ll*t[x].s[1][i]%mod)%mod; 46     } 47     if (l==1) { 48     for (int i=0;i<2;i++)  49         for (int j=0;j<3;j++) t[x].ch[j][i]=t[x].ch[j][i+1]; 50     for (int i=0;i<3;i++)  51         t[x].ch[i][2]=(t[x].ch[i][1]*1ll+t[x].ch[i][0]*1ll*a%mod+b*1ll*t[x].s[0][i]%mod)%mod; 52     } 53 } 54 inline void dec(int x,int l){     55     if (a==0) { 56     for (int i=1;i+1;i--) t[x].s[l][i+1]=t[x].s[l][i]; 57     t[x].s[l][0]=(t[x].s[l][1]-b*1ll*(t[x].r-t[x].l+1)%mod+mod)%mod; 58         if (l==0) { 59         for (int i=1;i+1;i--)  60         for (int j=0;j<3;j++) t[x].ch[i+1][j]=t[x].ch[i][j]; 61         for (int i=0;i<3;i++)  62         t[x].ch[0][i]=(t[x].ch[1][i]-b*1ll*t[x].s[1][i]%mod+mod)%mod; 63     } 64     if (l==1) { 65         for (int i=1;i+1;i--)  66         for (int j=0;j<3;j++) t[x].ch[j][i+1]=t[x].ch[j][i]; 67         for (int i=0;i<3;i++)  68         t[x].ch[i][0]=(t[x].ch[i][1]-b*1ll*t[x].s[0][i]%mod+mod)%mod; 69     } 70     return; 71     } 72     for (int i=1;i+1;i--) t[x].s[l][i+1]=t[x].s[l][i]; 73     t[x].s[l][0]=((t[x].s[l][2]*1ll-t[x].s[l][1]-b*1ll*(t[x].r-t[x].l+1)%mod)%mod*inv%mod+mod)%mod; 74     if (l==0) { 75         for (int i=1;i+1;i--)  76         for (int j=0;j<3;j++) t[x].ch[i+1][j]=t[x].ch[i][j]; 77     for (int i=0;i<3;i++)  78         t[x].ch[0][i]=((t[x].ch[2][i]*1ll-t[x].ch[1][i]-b*1ll*t[x].s[1][i]%mod)%mod*inv%mod+mod)%mod; 79     } 80     if (l==1) { 81         for (int i=1;i+1;i--)  82         for (int j=0;j<3;j++) t[x].ch[j][i+1]=t[x].ch[j][i]; 83     for (int i=0;i<3;i++)  84         t[x].ch[i][0]=((t[x].ch[i][2]*1ll-t[x].ch[i][1]-b*1ll*t[x].s[0][i]%mod)%mod*inv%mod+mod)%mod; 85     } 86 } 87 inline void pushback(int x,int y,int z) { 88     if (z>0)  89     for (int i=1;i<=z;i++) add(x,y); 90     if (z<0)  91     for (int i=-1;i>=z;i--) dec(x,y); 92 } 93 inline void pb(int x) { 94     for (int l=0;l<=1;l++){ 95     pushback(lc,l,t[x].lz[l]); 96     pushback(rc,l,t[x].lz[l]); 97     t[lc].lz[l]+=t[x].lz[l]; 98     t[rc].lz[l]+=t[x].lz[l]; 99     t[x].lz[l]=0;100     }101 }102 int A[maxn][4];103 inline void build (int x,int l,int r) {104     t[x].l=l,t[x].r=r;105     if (l==r) {106     for (int i=0;i<3;i++) {107         t[x].s[0][i]=A[l-1][i+1];108         t[x].s[1][i]=A[l+1][i+1];109     }110     for (int i=0;i<3;i++) 111         for (int j=0;j<3;j++) 112         t[x].ch[i][j]=t[x].s[0][i]*1ll*t[x].s[1][j]%mod;113     return ;114     }115     build(lc,l,mid);build(rc,mid+1,r);116     update(x);117 }118 inline void add(int x,int x1,int y1,int y,int z) {119     int l=t[x].l,r=t[x].r;120     if (l>y1||r
          
           y1||r
           
            >=1,x++) 163 if (y&1) ans=ans*f[x];164 return ans;165 }166 marix mx,my;167 int get(int x){168 marix tmp=my*pow(A[x][0]-2);169 A[x][1]=tmp.a[0][1];170 A[x][2]=tmp.a[0][0];171 }172 int main(){173 int n,q;174 scanf("%d%d%d%d",&n,&q,&a,&b);175 inv=power(a,mod-2);176 mx.r=mx.c=3;mx.a[0][0]=1,mx.a[1][0]=a,mx.a[2][0]=b;177 mx.a[0][1]=1,mx.a[2][2]=1;178 for (int i=1;i<=32;i++) {179 f[i]=mx;180 mx=mx*mx;181 }182 my.r=1;my.c=3;183 my.a[0][0]=2,my.a[0][1]=1,my.a[0][2]=1;184 for (int i=1;i<=n;i++) {185 scanf("%d",A[i]);186 get(i);187 A[i][3]=(A[i][2]*1ll+A[i][1]*1ll*a+b)%mod;188 }189 build(1,2,n-1);190 char opt[10];191 while (q--) {192 int l,r;193 scanf("%s",opt);194 switch(opt[0]) {195 case 'p':196 scanf("%d%d",&l,&r);197 add(1,l+1,r+1,0,1);198 add(1,l-1,r-1,1,1);199 break;200 case 'm':201 scanf("%d%d",&l,&r);202 add(1,l+1,r+1,0,-1);203 add(1,l-1,r-1,1,-1);204 break;205 case 'q':206 scanf("%d%d",&l,&r);207 printf("%d\n",que(1,l+1,r-1));208 break;209 }210 }211 return 0;212 }