感觉题意有坑
害我看了半天
题目原文：
一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k棵常青树。
本来以为要刚好 k 颗，不能多了
结果看着样例一脸懵逼
才发现多的可以不管
比如有一行有 a 颗树，那么从这 a 颗中随便取 k 颗出来都是一种方案
所以有 C[ a ] [ k ] 种方案
终于看懂题意了，然后看看数据范围
靠，这么大怎么搞？
果断放弃，看题解去了
看着题解半天才懂，我太菜了 题解
可以发现树的数量不大
所以考虑把树的坐标离散化
考虑一个点的四个方向的树对它的贡献
设四个方向的树的数量为 u,d,l,r
那么总的贡献就是 C[u][k] * C[d][k] * C[l][k] * C[r][k]
考虑从左到右，从下到上的顺序扫描
同一个 x 坐标的的相邻两个树的中间空地
u和d是不变的
会变的是l,r
如果要一次计算一段空地的总方案数则需要对C[l][k],C[r][k]求和后再乘上 上面下面的方案
用树状数组来维护一段 y 坐标的C值
核心代码，实现维护一段 y 坐标的C值（重点）
for(int i=1;i<=w;i++)//此时每颗树已经离散好了 { //注意树状数组维护的是一段y坐标的C的和 if(i==1||a[i].x!=a[i-1].x) tt=0; tt++;//存当前x坐标下面已经经过了多少棵树 int le=a[i].y,v=0; if( (++h[le]/*h存当前xy坐标的左边一段已经经过了多少棵树*/)>=K && cnt[le]/*cnt[i]存y坐标为i的树的数量，即一行的树的数量*/-h[le]/*减h[le]是求出当前xy坐标右边一段的树的数量*/>=K ) v=(1ll*C[ h[le] ][K]*C[ cnt[le]-h[le] ][K])%mo;//如果有贡献才计算 change(le,v-r[le]/*r存的是同一高度上一次v的值*/); r[le]=v;//把此行多增加的值加入树状数组并更新r数组 if(i==w||a[i].x!=a[i+1].x||a[i+1].y-a[i].y<=1||tt<K||tot[a[i].x]/*tot存的是x坐标为i的树的数量，即一列的树的数量*/-tt<K) continue;//注意一堆判断 Ans=(Ans+1ll*C[tt][K]*C[ tot[a[i].x]-tt ][K]/*u和d可以直接求出来*/%mo * ( query(a[i+1].y-1)-query(a[i].y)/*一段l和r的贡献用树状数组一次性求出来*/ )%mo)%mo; }
注释一堆...
来一发没注释的版本：
for(int i=1;i<=w;i++) { if(i==1||a[i].x!=a[i-1].x) tt=0; tt++; int le=a[i].y,v=0; if( (++h[le])>=K&&cnt[le]-h[le]>=K ) v=(1ll*C[ h[le] ][K]*C[ cnt[le]-h[le] ][K])%mo; change(le,v-r[le]); r[le]=v; if(i==w||a[i].x!=a[i+1].x||a[i+1].y-a[i].y<=1||tt<K||tot[a[i].x]-tt<K) continue; Ans=(Ans+1ll*C[tt][K]*C[ tot[a[i].x]-tt ][K]%mo*( query(a[i+1].y-1)-query(a[i].y) )%mo)%mo; }
然后就是离散化的操作和计算出cnt，tot和C的处理了
完整代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; const long long mo=2147483648; int w,C[N][17],tmp[N],tot[N],cnt[N],h[N],r[N],T[N],col,K; long long Ans; struct data { int x,y; }a[N];//存树的坐标 inline bool cmp1(const data &a,const data &b){ return a.x!=b.x ? a.x<b.x : a.y<b.y; }//按x,y排序 inline bool cmp2(const data &a,const data &b){ return a.y!=b.y ? a.y<b.y : a.x<b.x; }//按y,x排序 //树状数组的操作 inline void change(int x,int v){ while(x<=col) T[x]+=v,x+=(x&-x); } inline int query(int x){ int res=0; while(x) res+=T[x],x-=(x&-x); return res; } inline void pre()//预处理C { C[0][0]=1; for(int i=1;i<=w;i++) { C[i][0]=1; for(int j=1;j<=min(i,K);j++) C[i][j]=C[i-1][j]+C[i-1][j-1]; } } int main() { read(); read(); w=read(); for(int i=1;i<=w;i++) a[i].x=read(),a[i].y=read(); K=read(); pre(); sort(a+1,a+w+1,cmp1);//按xy排序 int tt=0; for(int i=1;i<=w;i++) { if(i==1||a[i].x!=a[i-1].x) tt++; tmp[i]=tt; } for(int i=1;i<=w;i++) tot[ a[i].x=tmp[i] ]++;//把x离散顺便计算tot sort(a+1,a+w+1,cmp2); tt=0;//按yx排序 for(int i=1;i<=w;i++) { if(i==1||a[i].y!=a[i-1].y) tt++; tmp[i]=tt; } for(int i=1;i<=w;i++) cnt[ a[i].y=tmp[i] ]++;//把y离散顺便计算cnt col=a[w].y;//树状数组的上限 sort(a+1,a+w+1,cmp1);//重新xy排序 for(int i=1;i<=w;i++)//注释之前代码有了，不再重复 { if(i==1||a[i].x!=a[i-1].x) tt=0; tt++; int le=a[i].y,v=0; if( (++h[le])>=K&&cnt[le]-h[le]>=K ) v=(1ll*C[ h[le] ][K]*C[ cnt[le]-h[le] ][K])%mo; change(le,v-r[le]); r[le]=v; if(i==w||a[i].x!=a[i+1].x||a[i+1].y-a[i].y<=1||tt<K||tot[a[i].x]-tt<K) continue; Ans=(Ans+1ll*C[tt][K]*C[ tot[a[i].x]-tt ][K]%mo*( query(a[i+1].y-1)-query(a[i].y) )%mo)%mo; } printf("%lld",Ans); return 0; }