题目大意：有一个长度为n的序列，有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c，2.R a b表示将[a,b]区间内所有元素变成相反数，3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。

思路：显然需要用线段树维护一个数组sum[c]表示选c个数相乘的方案总和。合并的时候只要枚举c，然后枚举左边选几个数然后和右边的乘起来累加进去就好了。取反实际上就是把所有c为奇数的取反，关键是区间加。对于[l,r]，区间+x，那么枚举c。注意到形式是这样的： newsum[c]=Σ(a1+x)(a2+x)...(ac+x)，然后按照x的次数合并同类项，可以发现这个东西可以通过x^k，组合数C(r-l+1,k)和oldsum[c-k]得到答案。k为x的次数。其余就是普通的线段树了。注意：推标记时要注意顺序。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 150000
#define mod 19940417
#define ll long long
using namespace std;

int lazy[N],zhs[N][21],size[N];
struct node{int sum[21];}ans[N];
bool rev[N];

int read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void add(int &x,int y)
{
    x+=y;
    if (x>=mod) x-=mod;
}

void up_date(int k)
{
     for (int i=1;i<=20;i++)
     {
         ans[k].sum[i]=0;
         for (int j=1;j<i;j++) add(ans[k].sum[i],(ll)ans[k<<1].sum[j]*ans[k<<1|1].sum[i-j]%mod);
         add(ans[k].sum[i],ans[k<<1].sum[i]);add(ans[k].sum[i],ans[k<<1|1].sum[i]);
     }
}

void ins(int k,int val)
{
     add(lazy[k],val);
     for (int i=20;i;i--)
     {
         int x=val,j;
         for (j=i-1;j;j--,x=(ll)x*val%mod)
             add(ans[k].sum[i],(ll)x*ans[k].sum[j]%mod*zhs[size[k]-j][i-j]%mod);
         add(ans[k].sum[i],(ll)x*zhs[size[k]][i]%mod);
     }
}

void turn(int k)
{
    int i; rev[k]^=1;
    if (lazy[k]) lazy[k]=mod-lazy[k];
    for (i=19;i>0;i-=2) if (ans[k].sum[i]) ans[k].sum[i]=mod-ans[k].sum[i];
}

void build(int l,int r,int cur)
{
     size[cur]=r-l+1;
     if (l==r) {ans[cur].sum[1]=read()%mod;return;}
     int mid=(l+r)>>1;
     build(l,mid,cur<<1),build(mid+1,r,cur<<1|1),up_date(cur);
}

void push_down(int k)
{
    if (rev[k]) turn(k<<1),turn(k<<1|1),rev[k]=0;
    if (lazy[k])ins(k<<1,lazy[k]),ins(k<<1|1,lazy[k]),lazy[k]=0;
}


void fan(int l,int r,int k,int x,int y)
{
    if (l==x && r==y){ turn(k); return; }
    int mid=l+r>>1; push_down(k);
    if (y<=mid) fan(l,mid,k<<1,x,y);
    else if (x>mid) fan(mid+1,r,k<<1|1,x,y);
         else fan(l,mid,k<<1,x,mid),fan(mid+1,r,k<<1|1,mid+1,y);
    up_date(k);
}

void jia(int L,int R,int cur,int l,int r,int val)
{
    if (l==L && r==R) {ins(cur,val);return;}
    int mid=(L+R)>>1; push_down(cur);
    if (r<=mid) jia(L,mid,cur<<1,l,r,val);
    else if (l>mid) jia(mid+1,R,cur<<1|1,l,r,val); 
         else jia(L,mid,cur<<1,l,mid,val),jia(mid+1,R,cur<<1|1,mid+1,r,val);
    up_date(cur);
}

node ask(int L,int R,int cur,int l,int r,int val)
{
     if (l==L && r==R) return ans[cur];
     int mid=(L+R)>>1; push_down(cur);
     if (l>mid) return ask(mid+1,R,cur<<1|1,l,r,val);
     else if (r<=mid) return ask(L,mid,cur<<1,l,r,val);
          else
          {
              node x=ask(L,mid,cur<<1,l,mid,val),y=ask(mid+1,R,cur<<1|1,mid+1,r,val),t;
              for (int i=1;i<=val;i++)
              {
                  t.sum[i]=(x.sum[i]+y.sum[i])%mod;
                  for (int j=1;j<i;j++) add(t.sum[i],(ll)x.sum[j]*y.sum[i-j]%mod);
              }
              return t;
          }
}

int main()
{
    int n=read(),m=read(),i,j;
    zhs[0][0]=1;
    for (i=1;i<=n;i++)
    {
        zhs[i][0]=1;
        for (j=1;j<=i && j<=20;j++) zhs[i][j]=(zhs[i-1][j-1]+zhs[i-1][j])%mod;
    }
    build(1,n,1);
    while (m--)
    {
          char ch=getchar();
          while (ch<'A' || ch>'Z') ch=getchar();
          if (ch=='I')
          {
               int x=read(),y=read(),z=read()%mod;
               if (z<0) z+=mod; jia(1,n,1,x,y,z);
          }
          if (ch=='R')
          {
              int x=read(),y=read();
              fan(1,n,1,x,y);
          }
          if (ch=='Q')
          {
              int x=read(),y=read(),z=read();
              printf("%d\n",ask(1,n,1,x,y,z).sum[z]);
          }
    }
    return 0;
}