题目：有n个女生，每个女生都有一个教室，有m个询问[l,r]，问你拜访该区间的女生的教室有多少种方案，对1e9+7取模
思路：num表示该教室的女生的人数，那么答案就是(r-l+1)！/(num1!*num2!....)
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<list> #include<numeric> using namespace std; #define PI acos(-1.0) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f #define mm(a,b) memset(a,b,sizeof(a)) #define PP puts("*********************"); template<class T> T f_abs(T a){ return a > 0 ? a : -a; } template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; } template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} // 0x3f3f3f3f3f3f3f3f // 0x3f3f3f3f const LL MOD=1000000007; const int maxn=3e4+50; struct Ask{ int L,R,id; }ask[maxn]; LL ans[maxn]; int arr[maxn],num[maxn];//从1开始计数 int n,m,siz;//n个数，m个询问，块的大小 LL Inv[maxn],F[maxn]; bool cmp(Ask a,Ask b){ if(a.L/siz!=b.L/siz) return a.L/siz<b.L/siz; else return a.R<b.R; } void solve(){ LL temp=1; mm(num,0); int L=1,R=0; for(int i=1;i<=m;i++){ while(R<ask[i].R){ R++; num[arr[R]]++; temp=temp*Inv[num[arr[R]]]%MOD; } while(R>ask[i].R){ temp=temp*(LL)num[arr[R]]%MOD; num[arr[R]]--; R--; } while(L<ask[i].L){ temp=temp*(LL)num[arr[L]]%MOD; num[arr[L]]--; L++; } while(L>ask[i].L){ L--; num[arr[L]]++; temp=temp*Inv[num[arr[L]]]%MOD; } int x=ask[i].R-ask[i].L+1; ans[ask[i].id]=temp*F[x]%MOD;; } } int main(){ int T; Inv[1]=1; F[0]=F[1]=1; for(int i=2;i<maxn;i++){ Inv[i]=(LL)(MOD-MOD/i)*Inv[MOD%i]%MOD; F[i]=F[i-1]*(LL)i%MOD; } scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&arr[i]); for(int i=1;i<=m;i++){ ask[i].id=i; scanf("%d%d",&ask[i].L,&ask[i].R); } siz=(int)sqrt(n*1.0); sort(ask+1,ask+m+1,cmp); solve(); for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); } return 0; }