首页 > 代码库 > hdu 5145

hdu 5145

2024-08-07 22:25:56   213人阅读

[l,r] = (r-l+1)!/(num[1]!*num[2]!*num[3]!*……*num[n])

num[i] 表示 [l,r]中i 的个数

[l,r] = [l-1,r]*(r-l+1)/(++num[a[l]])

[l,r] = [l-1,r]*(num[a[l-1]]--)/(r-l+2)

预处理 [1..n]的逆元

离线读进所有询问,将l/sqrt(n)当第一关键字,r当第二关键字进行排序,然后直接暴力即可.

复杂度证明:

l/sqrt(n)<=sqrt(n) 也就是说最多只有sqrt(n)个“块”,快里面的r都是升序的 所以r在每个块中最多遍历n次 一共有sqrt(n)块,所以r遍历了n*sqrt(n)

每个块里面的l最多相差sqrt(n),所以l只要遍历sqrt(n)次,有t个询问,所以l遍历了t*sqrt(n)次

所以最坏的复杂度为O((t+n)*sqrt(n));

  1 #include <cstdio>  2 #include <cstring>  3 #include <cmath>  4 #include <algorithm>  5 using namespace std;  6 #define N 30000  7 const int mod = (int)(1e9+7);  8 long long nv[N+20];  9 long long ans[N+20]; 10 long long res; 11 int L,R; 12 long long exgcd(long long a,long long b,long long &x,long long &y) 13 { 14     long long temp,d; 15     if (b==0) 16     { 17         x=1; 18         y=0; 19         return a; 20     } 21     d=exgcd(b,a%b,x,y); 22     temp=x-a/b*y; 23     x=y; 24     y=temp; 25     return d; 26 } 27 struct Node{ 28     int l,r,b,index; 29 }q[N+20]; 30 int a[N+20]; 31 int num[N+20]; 32 bool cmp(const Node &a,const Node &b){ 33     return a.b<b.b||(a.b==b.b&&a.r<b.r); 34 } 35 void add(int l,int r){ 36     if (l<L&&r<R){ 37         for (L=L-1;L>=l;L--){ 38             num[a[L]]++; 39             res = res * (R-L+1) % mod; 40             res = res * nv[num[a[L]]] % mod; 41         } 42         L++; 43         for (R=R;R>r;R--){ 44             res = res * num[a[R]] % mod; 45             res = res * nv[R-L+1] % mod; 46             num[a[R]]--; 47         } 48     } 49     if (l<L&&r>=R){ 50         for (L=L-1;L>=l;L--){ 51             num[a[L]]++; 52             res = res * (R-L+1) % mod; 53             res = res * nv[num[a[L]]] % mod; 54         } 55         L++; 56         for (R=R+1;R<=r;R++){ 57             num[a[R]]++; 58             res = res * (R-L+1) % mod; 59             res = res * nv[num[a[R]]] % mod; 60         } 61         R--; 62     } 63    if (l>=L&&r<R){ 64         for (R=R;R>r;R--){ 65             res = res * num[a[R]] % mod; 66             res = res * nv[R-L+1] % mod; 67             num[a[R]]--; 68         } 69         for (L=L;L<l;L++){ 70             res = res * num[a[L]] % mod; 71             res = res * nv[R-L+1] % mod; 72             num[a[L]]--; 73         } 74     } 75     if (l>=L&&r>=R){ 76         for (R=R+1;R<=r;R++){ 77             num[a[R]]++; 78             res = res * (R-L+1) % mod; 79             res = res * nv[num[a[R]]] % mod; 80         } 81         R--; 82         for (L=L;L<l;L++){ 83             res = res * num[a[L]] % mod; 84             res = res * nv[R-L+1] % mod; 85             num[a[L]]--; 86         } 87     } 88 } 89 int main(){ 90     for (int i=0;i<=N;i++){ 91         long long X,Y; 92         exgcd(i,mod,X,Y); 93         nv[i] = (X%mod+mod) % mod; 94     } 95     int t; 96     for (scanf("%d",&t);t;t--){ 97         int n,m; 98         scanf("%d%d",&n,&m); 99         for (int i=1;i<=n;i++) scanf("%d",&a[i]);100         int siz = (int)sqrt(n);101         for (int i=1;i<=m;i++){102             int l,r;103             scanf("%d%d",&l,&r);104             q[i].l = l;105             q[i].r = r;106             q[i].b = l/siz;107             q[i].index = i;108         }109         sort(q+1,q+1+m,cmp);110         L = 0, R = 0;111         res = 1;112         memset(num,0,sizeof(num));113         num[0] = 1;114         for (int i=1;i<=m;i++){115             add(q[i].l,q[i].r);116             ans[q[i].index] = res;117         }118         for (int i=1;i<=m;i++) printf("%I64d\n",ans[i]);119     }120 }

hdu 5145


联系
我们