hdu5145 莫队算法

浏览数：22 / 时间：2015年06月08日

这题说的是个了n个数字然后在L 和R 区间内的数字的排列有多少种方案，

这里我们通过将这n长度的字符串分成sqrt(n) 块然后一个属性他们的l 属于那个快以这个为第一关键字，然后在按照R 为第二个关键字，然后sort 每个查询区间

我们知道当L他们属于一块内的时候， R 是逐渐递增的，那么转移了 sqrt(n)*a+n个然后以此方案接近复杂度接近n^(1.5)

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = 30005;
const LL mod =  1000000007;
struct seg{
  int L,R,id;
}P[maxn];
int b[maxn];
void gcd(LL a, LL b, LL &d, LL &x, LL &y ){
    if(b==0){
          d=a; x=1; y=0;
    }else{
        gcd(b,a%b,d,y,x); y-=x*(a/b);
    }
}
LL inv( LL a){
  LL d, x,y;
     gcd(a,mod,d,x,y);
     return d==1?(x+mod)%mod:-1;
}
LL A[maxn],ans[maxn],num[maxn],aa,niA[maxn];
int C[maxn];
bool cmp(seg A, seg B){
    return b[A.L]==b[B.L]?A.R<B.R:b[A.L]<b[B.L];
}
void update(int x, int add){
      aa= (aa *  niA[ num[x] ] )%mod;
      num[x]+=add;
      aa= (aa * A[num[x] ] )%mod;
}
void solve(int m){
    memset(num,0,sizeof(num));
     aa=1;
    LL L=1, R=0;
    for(int i=0; i<m; i++){
         while(R<P[i].R){
            R++;
            update(C[R],1);
         }
         while(R>P[i].R){
            update(C[R],-1);R--;
         }
         while(L<P[i].L){
              update(C[L],-1);L++;
         }
         while(L>P[i].L){
            L--;
            update(C[L],1);
         }
         ans[ P[i].id ]=(inv(aa)*A[ P[i].R-P[i].L+1 ])%mod;
    }
    for(int i=0; i<m; i++){
         printf("%I64d\n",ans[i]);
    }
}
int main()
{
   A[0]=1; niA[0]=inv(1);
   for(LL i=1; i<maxn-1; i++){

       A[i]=(A[i-1]*i)%mod;
       niA[i] = inv(A[i]);
   }
    int cas;
    scanf("%d",&cas);
    for(int cc=1; cc<=cas; ++cc){
         int n,m;
         scanf("%d%d",&n,&m);
         int boloc=sqrt(n+0.5);
         for(int i=1; i<=n; i++){
             b[i]=(i-1)/boloc+1;
         }
         for(int i=1; i<=n; i++)scanf("%d",&C[i]);
        for(int i=0; i<m; i++){
             P[i].id=i; scanf("%d%d",&P[i].L,&P[i].R);
        }
        sort(P,P+m,cmp);
        solve(m);
    }
    return 0;
}