题意：

给你1-n属于的班级

给你一个[l,r]区间

问你如果要访问这个区间内所有的女生

有多少种走不同教室的方法

 

思路：

和小z差不多 只不过这个维护的是阶乘

找出来公式之后莫队直接离线处理

 

莫队更多的是离线排序优化的思想

把所有查询排序处理 然后逐个处理 可以应用到很多方面

 

1 #include
     
        2 #define cl(a,b) memset(a,b,sizeof(a))  3 #define debug cerr<<#a<<"=="<
      <
       
         pii;  7   8 const int maxn=3e4+10;  9 const int mod=1e9+7; 10  11 int n,m; 12 ll inv[maxn]; 13 ll a[maxn]; 14 ll res[maxn]; 15 ll num[maxn]; 16  17 struct query 18 { 19     int l,r,id,sqr; 20     bool operator < (const query &a) const 21     { 22         if(a.sqr==sqr) return r
        
         >=1; 38     } 39     return ans; 40 } 41  42 ll getinv(ll x) 43 { 44     return quick_mod(x,mod-2); 45 } 46  47 void init() 48 { 49     for(int i=1; i<=maxn; i++) 50     { 51         inv[i]=getinv(i); 52     } 53 } 54  55 void solve() 56 { 57     int l=1,r=1; 58     ll ans=1; 59     cl(num,0); 60     num[a[1]]++; 61     for(int i=1; i<=m; i++) 62     { 63         while(r
         
          q[i].l) 70         { 71             l--; 72             num[a[l]]++; 73             ans=ans*(r-l+1)%mod*inv[num[a[l]]]%mod; 74         } 75         while(r>q[i].r) 76         { 77             ans=ans*num[a[r]]%mod*inv[r-l+1]%mod; 78             num[a[r]]--; 79             r--; 80         } 81         while(l