题意： cases T(1≤T≤10) (0<n,m≤30000) (0<ai≤30000)
n个数ai 表示n个女孩所在教室
m次询问 [L,R]（1 <= L <= R <= n）
问访问所有女孩的顺序方案数(进教室顺序)为多少(一次进教室只能访问一个人)
分析：
莫队算法 + 排列数
一个区间内的方案数为 C(m,c1)*C(m-c1,c2)*C(m-c1-c2,c3)*....*C(cn,cn)
每次转移通过下式：
C(m+1,n+1) = C(m,n) * (m+1/n+1)
C(m,n) = C(m+1,n+1) * (n+1/m+1) （对于缩小的过程而言）
因为需要对大素数取模，除法就是乘上对应的乘法逆元，故先用费马小定理
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int MOD = ;
const int MAXN = ;
const int MAXM = ;
struct Query
{
int L,R,id;
}node[MAXM];
struct Ans
{
long long a;
}ans[MAXM];
int a[MAXN],num[MAXN];
long long inv[MAXN];//乘法逆元
int t,n,m,unit;
void work()
{
long long temp = ;
memset(num,,sizeof(num));
int L = , R = ;
for(int i = ; i < m ; i++)
{
while(R < node[i].R)//C(m+1,n+1) = C(m,n)*(m+1/n+1)
{
R++;
num[a[R]]++;
temp = temp * (R - L + ) % MOD * inv[num[a[R]]] % MOD;
}
while(R > node[i].R)//C(m,n) = C(m+1,n+1)*(n+1/m+1)
{
temp = temp * num[a[R]] % MOD * inv[R - L + ] % MOD;
num[a[R]]--;
R--;
}
while(L < node[i].L)//C(m,n) = C(m+1,n+1)*(n+1/m+1)
{
temp = temp * num[a[L]] % MOD * inv[R - L + ] % MOD;
num[a[L]]--;
L++;
}
while(L > node[i].L)//C(m+1,n+1) = C(m,n)*(m+1/n+1)
{
L--;
num[a[L]]++;
temp = temp * (R - L + ) % MOD * inv[num[a[L]]] % MOD;
}
ans[node[i].id].a = temp;
}
}
bool cmp(Query a,Query b)
{
if(a.L/unit != b.L/unit) return a.L/unit < b.L/unit;
else return a.R < b.R;
}
void Init()//femat
{
inv[] = ;
for(int i = ; i < MAXN; i++)
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
}
int main()
{
Init();
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++)
scanf("%d",&a[i]);
for(int i = ; i < m; i++)
{
scanf("%d%d",&node[i].L,&node[i].R);
node[i].id = i;
}
unit = (int)sqrt(n);
sort(node,node+m,cmp);
work();
for(int i = ; i < m ;i++)
printf("%lld\n",ans[i].a);
}
}