bzoj1227: [SDOI2009]虔诚的墓主人（树状数组，组合数）

首先，对于每一块墓地，如果上下左右各有$a,b,c,d$棵树，那么总的虔诚度就是$C_k^a*C_k^b*C_k^c*C_k^d$

那么我们先把所有的点都给离散，然后按$x$为第一关键字，$y$为第二关键字，那么同一横坐标的一定在连续的一段且纵坐标递增

那么对于同一横坐标的两棵常青树，在他们中间的所有空地都有可能满足条件，因为上面的常青树和下面的常青树数量是固定的，所以$C_k^a*C_k^b$的值也是固定的

那么我们就是需要快速求出一段区间里的$C_k^c*C_k^d$，那么我们可以考虑用树状数组来维护。这部分细节可以参考代码

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define int long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,mod=;

 int n,m,k,C[N][],tt=,ans,tmp[N],c[N],col,tot[N],cnt[N],r[N],h[N];

 struct node{int x,y;}a[N];

 inline bool cmp(const node &a,const node &b)

 {return a.x!=b.x?a.x<b.x:a.y<b.y;}

 inline bool cmp2(const node &a,const node &b)

 {return a.y!=b.y?a.y<b.y:a.x<b.x;}

 inline void add(int x,int y){

     for(;x<=col;x+=x&-x) (c[x]+=y)%=mod;

 }

 inline int query(int x){

     int res=;

     for(;x;x-=x&-x) (res+=c[x])%=mod;

     return res;

 }

 signed main(){

     //freopen("testdata.in","r",stdin);

     read();read();n=read();

     for(int i=;i<=n;++i) a[i].x=read(),a[i].y=read();

     k=read();

     for(int i=;i<=n;++i) C[i][]=;

     for(int i=;i<=n;++i)

     for(int j=;j<=min(i,k);++j)

     C[i][j]=C[i-][j]+C[i-][j-];

     sort(a+,a++n,cmp2);

     for(int i=;i<=n;++i)

     tmp[i]=(i==||a[i].y!=a[i-].y)?++tt:tt;

     for(int i=;i<=n;++i) cnt[a[i].y=tmp[i]]++;col=a[n].y;

     sort(a+,a++n,cmp);

     for(int i=;i<=n;++i)

     tmp[i]=(i==||a[i].x!=a[i-].x)?++tt:tt;

     for(int i=;i<=n;++i) tot[a[i].x=tmp[i]]++;

     for(int i=;i<=n;++i){

         if(i==||a[i].x!=a[i-].x) tt=;

         int dy=a[i].y,v=(++h[dy])>=k&&cnt[dy]-h[dy]>=k?

         1ll*C[h[dy]][k]*C[cnt[dy]-h[dy]][k]%mod:;++tt;

         add(dy,v-r[dy]),r[dy]=v;

         if(i==n||a[i].x!=a[i+].x||a[i+].y-a[i].y<=

         ||tt<k||tot[a[i].x]-tt<k) continue;

         (ans+=1ll*C[tt][k]*C[tot[a[i].x]-tt][k]%mod

         *(query(a[i+].y-)-query(a[i].y)))%=mod;

     }

     printf("%d\n",(ans>=?ans:ans+mod)%mod);

     return ;

 }

巴特西

bzoj1227: [SDOI2009]虔诚的墓主人（树状数组，组合数）

最新文章

热门文章