HDU_5145

题意

NPY如何怒草后宫群

思路

逆元打表、莫队算法、公式什么的是看网上别人的代码……

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define ll long long
#define eps 1e-7
#define mod 1000000007
#define NV 30030
ll len,n,q,ans[NV],inv[NV],cla[NV],cnt[NV];
ll l,r,tmp;
struct  modui
{
    ll l,r,id;
    bool operator < (const modui & b)const{
        return l/len==b.l/len? r<b.r : l<b.l;
    }
}md[NV];
ll quick_pow(ll x,ll n){
    ll ans=1;
    for(;n;n>>=1,x=(x*x)%mod)
        if(n&1)ans=(ans*x)%mod;
    return ans;
}
ll get_inv(ll a) {
    return quick_pow(a, mod - 2);
}
void add(ll x){
    cnt[cla[x]]++;
    tmp = tmp*(r-l+1)%mod*inv[cnt[cla[x]]]%mod;
}
void del(ll x){
    tmp = tmp*cnt[cla[x]]%mod*inv[r-l+1]%mod;
    cnt[cla[x]]--;
}
void work(){
    l=1,r=0,tmp=1;
    memset(cnt,0,sizeof(cnt));
    for(int i =0 ;i< q ;i++){
        while(md[i].r>r)add(++r);
        while(md[i].r<r){del(r);r--;}
        while(md[i].l>l){del(l);l++;}
        while(md[i].l<l)add(--l);
        ans[md[i].id] = tmp;
    }
}
int main(){
    int t;
    for(int i = 1 ;i<=30000 ; i++)
        inv[i]=get_inv((ll)i);
    for(cin>>t;t--;){
        scanf("%I64d%I64d",&n,&q);
        len=ceil(sqrt(n*1.0));
        for(int i=1 ;i<=n ;i++)
            scanf("%I64d",&cla[i]);
        for(int i=0 ; i<q ;i++){
            scanf("%I64d%I64d",&md[i].l,&md[i].r);
            md[i].id=i;
        }
        sort(md,md+q);
        work();
        for(int i=0 ; i < q ;i++)
            printf("%I64d\n",ans[i]);
    }
    
    return 0;
}