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

forever97 posted @ 2016年9月15日 20:15 in 算法-莫队算法 with tags 莫队算法乘法逆元 , 416 阅读

【题目链接】 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;
}