hdu5145 NPY and girls

时间:2023-02-03 14:22:30

人生中第一道莫队,本来以为是一道水题的。。

首先这题只有区间查询,没有修改操作,使用莫队比较明显,但统计答案有点麻烦。。

根据题意,在n个人里选m个不相同种类的人,设第i种人数量为ai,总方案为c(n,a1)*c(n-a1,a2)*c(n-a1-a2,a3)*...*c(n-a1-a2-...-an-1,an)。而我们要用O(1)的复杂度实现转移,那么我们可以用c(n,m)=c(n-1,m-1)*n/m来实现转移,在模意义下除法必须使用逆元,那么我们利用费马小定理预处理出每个值的逆元就好了。。

总的来说,莫队算法真的很神啊。。不仅思想简单,实现简单,复杂度还很优秀。。

//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf 1<<30
#define il inline
#define RG register
#define ll long long
#define eps 1e-9
#define rhl 1000000007LL
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; struct node{ int l,r,id,bl; }p[30010]; int a[30010],c[30010],n,m;
ll inv[30010],ans[30010]; il int gi(){
RG int x=0,q=0; RG char ch=getchar();
while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if (ch=='-') q=1,ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q ? -x : x;
} il int cmpt(const node &a,const node &b){ return a.bl<b.bl || (a.bl==b.bl && a.r<b.r); } il ll q_pow(RG ll a,RG ll b){ RG ll ans=1,x=a; while (b){ if (b&1) ans=ans*x%rhl; x=x*x%rhl,b>>=1; } return ans; } il void solve(){
RG int l=1,r=0; RG ll Ans=1;
for (RG int i=1;i<=m;++i){
while (l>p[i].l){ l--,c[a[l]]++,Ans=Ans*(ll)(r-l+1)%rhl*inv[c[a[l]]]%rhl; }
while (r<p[i].r){ r++,c[a[r]]++,Ans=Ans*(ll)(r-l+1)%rhl*inv[c[a[r]]]%rhl; }
while (l<p[i].l){ Ans=Ans*(ll)c[a[l]]%rhl*inv[r-l+1]%rhl,c[a[l]]--,l++; }
while (p[i].r<r){ Ans=Ans*(ll)c[a[r]]%rhl*inv[r-l+1]%rhl,c[a[r]]--,r--; }
ans[p[i].id]=Ans;
}
return;
} il void work(){
n=gi(),m=gi(); RG int block=sqrt(n*1.0); for (RG int i=1;i<=n;++i) a[i]=gi(),c[i]=0,ans[i]=0;
for (RG int i=1;i<=m;++i) p[i].l=gi(),p[i].r=gi(),p[i].id=i,p[i].bl=(p[i].l-1)/block+1;
sort(p+1,p+m+1,cmpt); solve(); for (RG int i=1;i<=m;++i) printf("%lld\n",ans[i]); return;
} int main(){
File("npy");
for (RG int i=1;i<=30000;++i) inv[i]=q_pow((ll)i,(ll)rhl-2);
RG int T=gi(); while (T--) work();
return 0;
}