hdu 5145(莫队算法+逆元)

NPY and girls

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 790    Accepted Submission(s): 280

Problem Description

NPY's

girlfriend blew him out!His honey doesn't love him any more!However, he

has so many girlfriend candidates.Because there are too many girls and

for the convenience of management, NPY numbered the girls from 1 to

n.These girls are in different classes(some girls may be in the same

class).And the i-th girl is in class ai.NPY wants to visit his girls

frequently.Each time he visits some girls numbered consecutively from L

to R in some order. He can only visit one girl every time he goes into a

classroom,otherwise the girls may fight with each other(-_-!).And he

can visit the class in any order.

Here comes the problem,(NPY doesn't

want to learn how to use excavator),he wonders how many different ways

there can be in which he can visit his girls.The different ways are

different means he visits these classrooms in different order.

Input

The first line contains the number of test cases T(1≤T≤10).

For each test case,there are two integers n,m(0<n,m≤30000) in the first line.N is the number of girls,and M is the number of times that NPY want to visit his girls.

The following single line contains N integers, a1,a2,a3,…,an, which indicates the class number of each girl. (0<ai≤30000)

The following m lines,each line contains two integers l,r(1≤l≤r≤n),which indicates the interval NPY wants to visit.

Output

For each visit,print how many ways can NPY visit his girls.Because the ans may be too large,print the ans mod 1000000007.

Sample Input

2

4 2

1 2 1 3

1 3

1 4

1 1

1

Sample Output

3

12

Source

BestCoder Round #22

题意:有n个班级,询问在[l,r]区间内班级女生的排列方式有多少种,比如说 1 1 2,那么就有三种 1 1 2 ，2 1 1，1 2 1。

题解:首次接触莫队算法。

莫队算法：可以解决一类静态，离线区间查询问题。http://blog.csdn.net/bossup/article/details/39236275

发明这个的人好强啊,没看懂分块，不过用起来的话还是会用模板的.[l,r]里面的数字假设有m个,每个班级有c[i]个人,那么排列组合的总数为 m!/ ( c[1]! * .......c[n]! ) 关键是怎么用莫对算法求解这个式子。当区间从 [l,r-1] - >[l,r]时，那么假设之前的区间[l,r-1]里面的排列数为 N1,那么[l,r]的结果应当为 N1*(r+l-1)/c[a[r]++] ,反之,当现在的区间从

[l,r+1]->[l,r]时,假设 [l,r+1]里面的排列数为 N2,那么当前[l,r]里面的排列数应该变成了 N2*c[a[r+1]++]/(r-l+1)个人.还有左边区间两种情况可以仿造这两种情况得出来。

由于有取模操作,所以除法要用上逆元.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1000000007;
const int N = 30005;
int n,m;
LL a[N];
LL inv[N];
LL Hash[N];
LL res[N];
struct Node{
    int l,r,sqr,id;
}node[N];
int cmp(Node a,Node b){
    if(a.sqr==b.sqr) return a.r<b.r;
    return a.l<b.l;
}
LL pow_mod(LL a,LL n){
    LL ans = 1;
    while(n){
        if(n&1) ans = ans*a%mod;
        a = a*a%mod;
        n>>=1;
    }
    return ans;
}
LL getinv(int x){
    return pow_mod(x,mod-2);
}
int main()
{
    int tcase;
    scanf("%d",&tcase);
    for(int i=1;i<=N;i++){
        inv[i] = getinv(i);
    }
    while(tcase--)
    {
        scanf("%d%d",&n,&m);
        int k = (int)sqrt(n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&node[i].l,&node[i].r);
            node[i].id = i;
            node[i].sqr = node[i].l/k;
        }
        sort(node+1,node+m+1,cmp);
        memset(Hash,0,sizeof(Hash));
        int l=1,r = 1;
        Hash[a[1]]++;
        LL ans = 1;
        for(int i=1;i<=m;i++){
            while(r<node[i].r){
                r++;
                Hash[a[r]]++;
                ans = ans*(r-l+1)%mod*inv[Hash[a[r]]]%mod;
            }
            while(l>node[i].l){
                l--;
                Hash[a[l]]++;
                ans = ans*(r-l+1)%mod*inv[Hash[a[l]]]%mod;
            }
            while(r>node[i].r){
                ans = ans*Hash[a[r]]%mod*inv[r-l+1]%mod;
                Hash[a[r]]--;
                r--;
            }
            while(l<node[i].l){
                ans = ans*Hash[a[l]]%mod*inv[r-l+1]%mod;
                Hash[a[l]]--;
                l++;
            }
            res[node[i].id] = ans;
        }
        for(int i=1;i<=m;i++){
            printf("%lld\n",res[i]);
        }
    }
    return 0;
}