题目大意:
就是有个人生赢家有好多女朋友,然后他还把这些女朋友排成了一个序列,并且还知道每个女朋友所在的班级。他要多次约一个区间的所有女朋友出去玩。(一个班的女朋友可以看做是相同的)现在,对于给定的每个区间,他有多少种约这个区间所有女朋友出去玩的方式(顺序)。
分析:
其实就是推一个公式:
对于区间
那么每次从
一开始这样交超时了,后来发现求的都是0~3e4的数关于1e9+7的逆元,所以选择加了一个记忆化,然后就AC了。但是要注意从一个区间转移到另一个区间的过程中,要先扩大区间,再减小区间,不然会出现负区间,导致答案错误。
代码:
#include<bits/stdc++.h>
using namespace std;
#define maxn 30040
#define mod 1000000007
int n,m,pos[maxn],a[maxn];
long long int num[maxn],ans,ppow[maxn];
long long int fast_pow(long long int x,long long int p)
{
if(ppow[x]!=-1)return ppow[x];
long long int ans=1,k=x;
while(p>0)
{
if(p&1)ans*=x;
x*=x;
x%=mod;
ans%=mod;
p>>=1;
}
ppow[k]=ans;
return ans;
}
struct mo
{
int l;int r;int id;long long int ans;
}p[maxn];
bool mo_cmp(mo a,mo b)
{
return pos[a.l]==pos[b.l] ? a.r<b.r : a.l<b.l;
}
bool id_cmp(mo a,mo b)
{
return a.id<b.id;
}
int main()
{
int t;
scanf("%d",&t);
memset(ppow,-1,sizeof(ppow));
while(t--)
{
scanf("%d%d",&n,&m);
int unit=sqrt(n);
memset(num,0,sizeof(num));
ans=1;
for(int i=0;i<=n;i++)pos[i]=i/unit;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++)
{
scanf("%d%d",&p[i].l,&p[i].r);
p[i].id=i;
}
sort(p,p+m,mo_cmp);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(r<p[i].r)
{
r++;num[a[r]]++;
ans*=(r-l+1);ans%=mod;
ans*=fast_pow( num[a[r]] , mod-2 );ans%=mod;
}
while(l>p[i].l)
{
l--;num[a[l]]++;
ans*=(r-l+1);ans%=mod;
ans*=fast_pow( num[a[l]] , mod-2 );ans%=mod;
}
while(l<p[i].l)
{
ans*=fast_pow( (long long int )(r-l+1) , mod-2 );ans%=mod;
ans*=num[a[l]];ans%=mod;
num[a[l]]--;l++;
}
while(r>p[i].r)
{
ans*=fast_pow( (long long int )(r-l+1) , mod-2 );ans%=mod;
ans*=num[a[r]];ans%=mod;
num[a[r]]--;r--;
}
p[i].ans=ans%mod;
}
sort(p,p+m,id_cmp);
for(int i=0;i<m;i++)
{
printf("%lld\n",p[i].ans);
}
}
}