题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5145
题目大意：给我们两个数n,q，分别代表有n个女生以及q个询问，然后给出n个女生所在的教室号，接着给出q个询问，每一个询问都是[L,R]，问我们在1~n的女生中访问L~R这几个女生可以的方案数，由于女生可能会几个出现在同一个教室，所以我们可以用排列组合去求解。
设在L~R这个区间中一共有m个教室的女生，一共有N个女生，每一个教室都有ci个女生，则方案数就是C(N, c1)*C(N-c1, c2)*C(N-c1-c2, c3)……C(cm, cm)。
显然暴力求组合数肯定是要超时的，所以我们要分块。
首先，小编先讲解一个关于组合数的推导：
1. C(m+1,n+1) = C(m,n)*(m+1/n+1)
2. C(m,n) = C(m+1,n+1)*(n+1/m+1)
1和2其实是一样的，写法不同而已，这两个式子在小编下面的推导中要用到。
假如我们知道了[l,r]的答案，则我们可以求得[l,r+1]：
cnt[i]表示在第i个教室的女生的个数，那么a[r+1]对答案的贡献相当于小编刚刚给出的组合数性质的第一个。
cnt[a[r]]++; tmp = tmp*(r-l+1)%MOD*inv[cnt[a[r]]]%MOD;
假如我们知道了[l,r]的答案，则我们可以求得[l-1,r]：
cnt[i]表示在第i个教室的女生的个数，那么a[l-1]对答案的贡献相当于小编刚刚给出的组合数性质的第二个。
tmp = tmp*cnt[a[r]]%MOD*inv[r-l+1]%MOD; cnt[a[r]]--;
那么我们知道[p,q]的答案，就可以反复运用上面小编给出的这两步推出[L,R]的答案。
接下来我们就可以用到莫队算法，把这n个数分成sqrt(n)个区间，算出这个q个询问的左端在那一块:pos = L/sqrt(n)，在记录下每一个询问的顺序之后，对这q个询问进行排序，以pos作为第一关键字，R作为第二关键字。然后我们就可以按照新的询问顺序求出所有询问的答案。
我们这个方法的复杂度为O(n^1.5)。
相信很多不太懂分块原理和莫队算法的同学都不知道这是为什么，也有可能有些同学连为什么要这样分块，为什么不直接按左端为第一关键字排序，小编这里就顺便讲解一下吧。
1)对于那些左端点属于同一个块的询问
i)因为r是递增的，最差情况q从块的最左端加到n，O(n)，一共n^0.5个块，所以这部分的复杂度是O(n^1.5)的
ii)p一次询问最多变化N^0.5,所以这部分的时间复杂度是O(Q*n^0.5)
2)从一个块跨越到另外一个块时
i)p最多变化2*n^0.5,最多跨越n^0.5，这部分复杂度是O(n)
ii)最差情况下，q从n移动到最左端
n和Q范围一样，所以整个算法复杂度是O(n^1.5)
这就是我们分块的神奇之处，复杂度为O(n^1.5)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 10000;
const LL MOD = 1e9+7;
LL Pow_mod(LL a,LL b)
{LL ans = 1;while(b){if(b&1) ans = (ans*a)%MOD;b >>= 1;a = (a*a)%MOD;}return ans;
}
LL Inv(LL a)
{return Pow_mod(a,MOD-2);
}
int per;
struct Query
{int l,r,id;bool operator < (const struct Query a)const{return l/per == a.l/per? r < a.r: l/per < a.l/per;}
};
Query query[30030];
LL ans[30030],inv[30030];
int a[30030],cnt[30030];
int main()
{for(int i = 1; i <= 30000; ++i)inv[i] = Inv(i);int t,n,q;scanf("%d",&t);while(t--){scanf("%d%d",&n,&q);per = sqrt(n*1.0);for(int i = 1; i <= n; ++i)scanf("%d",&a[i]);for(int i = 0; i < q; ++i){scanf("%d%d",&query[i].l,&query[i].r);query[i].id = i;}sort(query,query+q);int l = 1, r = 0;LL tmp = 1;memset(cnt,0,sizeof(cnt));for(int i = 0; i < q; ++i){while(r < query[i].r){++r;cnt[a[r]]++;tmp = tmp*(r-l+1)%MOD*inv[cnt[a[r]]]%MOD;}while(l > query[i].l){--l;cnt[a[l]]++;tmp = tmp*(r-l+1)%MOD*inv[cnt[a[l]]]%MOD;}while(r > query[i].r){tmp = tmp*cnt[a[r]]%MOD*inv[r-l+1]%MOD;cnt[a[r]]--;--r;}while(l < query[i].l){tmp = tmp*cnt[a[l]]%MOD*inv[r-l+1]%MOD;cnt[a[l]]--;++l;}ans[query[i].id] = tmp;}for(int i = 0; i < q; ++i)printf("%I64d\n",ans[i]);}return 0;
}