HDU 5145 NPY and girls（莫队算法+乘法逆元）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5145

【题目大意】

　　给出一个数列，每次求一个区间数字的非重排列数量。答案对1e9+7取模。

【题解】

　　我们发现每次往里加入一个新的数字或者减去一个新的数字，前后的排列数目是可以通过乘除转移的，所以自然想到用莫队算法处理。因为答案要求取模，所以在用除法的时候要计算逆元。

【代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

const int N=1000100;

using namespace std;

typedef long long LL;

const LL mod=1e9+7;

int pos[N],num[N],n,m,limit,i,l,r,S[N];

LL rf[N]={0,1};

LL ans,k,len;

inline void init(){for(int i=2;i<N;i++)rf[i]=rf[mod%i]*(mod-mod/i)%mod;}

struct Q{

    int l,r,id;LL ans;

    friend bool operator < (const Q &a,const Q &b){

        return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&a.r<b.r);

    }

}ask[N];

inline bool cmp(const Q &a,const Q &b){return a.id<b.id;}

inline void read(int&a){

    char ch;while(!((ch=getchar())>='0')&&(ch<='9'));

    a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';

}

inline void modify(int p,LL &ans,int add){

    if(add>0)S[num[p]]++,ans=ans*(++len)%mod*rf[S[num[p]]]%mod;

    else ans=ans*S[num[p]]%mod*rf[len--]%mod,S[num[p]]--;

}

int T;

int main(){

    init(); read(T);

    while(T--){

        read(n);read(m);

        limit=(int)sqrt(n+0.5);

        memset(S,0,sizeof(S));

        for(i=1;i<=n;i++){read(num[i]);pos[i]=(i-1)/limit+1;}

        for(i=1;i<=m;i++){read(ask[i].l);read(ask[i].r);ask[i].id=i;}

        sort(ask+1,ask+m+1); ans=1; len=0;

        for(i=1,l=1,r=0;i<=m;i++){

            while(r<ask[i].r)modify(++r,ans,1);

            while(r>ask[i].r)modify(r--,ans,-1);

            while(l<ask[i].l)modify(l++,ans,-1);

            while(l>ask[i].l)modify(--l,ans,1);

            ask[i].ans=ans;

        }sort(ask+1,ask+m+1,cmp);

        for(i=1;i<=m;i++)printf("%lld\n",ask[i].ans);

    }return 0;

}