专栏首页wymP2154 [SDOI2009]虔诚的墓主人

P2154 [SDOI2009]虔诚的墓主人

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/101852271

题意: 给出n,m ( n,m<=1e9 ), 表示一个矩阵 (0,0)到(n,m)有 w 棵(w<=1e5)常青树,求这个矩阵的虔诚度,虔诚度的定义如下: 对于矩阵上任意一点,正上下左右方向有恰好 k 棵(k<=10)常青树的方案数。 例如 某一点四个方向依次有 2,2,2,3此时 k = 2, 则虔诚度为 3。 保证 w 棵常青树位置各不相同,并给出w个坐标每个代表一颗常青树。答案对2,147,483,648 取模。

解: 先离散化坐标, 先按 y ,x 为一二键值从小到大排序, 给 y 离散化,并记录每 列有多少常青树, 再按照x,y为一二键值排序,给 x离散化,记录每行有多少常青树。显然,每个空地方案数 = C(up,k)*C(down,k)*C(left,k)*C(right,k)%MOD;

接下来,对每一行而言,相邻两常青树之间的空地 左右常青树的个数是相同的,这些空地上下常青树的个数不同,用树状数组记录每列的贡献,详见代码。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=2147483648;
const int MAXN=100005;
ll num[MAXN];
ll num2[MAXN];
ll n,m,w,k;
struct N{
	ll x,y;
}point[MAXN];
bool cmp1(N p1,N p2){
	if(p1.x!=p2.x)return p1.x<p2.x;
	return p1.y<p2.y;
}         
bool cmp2(N p1,N p2){
	if(p1.y!=p2.y)return p1.y<p2.y;
	return p1.x<p2.x;
}    
ll h[MAXN],l[MAXN]; 
ll r[MAXN];
ll b[MAXN],tmp[MAXN];
void add(int x,ll v){
	while(x<MAXN){
		b[x]+=v;
		x+=(x&(-x));
	}
}
ll sum(int x){
	ll res = 0;
	while(x){
		res+=b[x];
		x-=(x&(-x));
	}
	return res;
}     
ll C[MAXN][20];
int main()
{
	ll cnt = 0;
	scanf("%lld %lld",&n,&m);
	scanf("%lld",&w);
	for(int i=1;i<=w;i++)scanf("%lld %lld",&point[i].x,&point[i].y);
	scanf("%lld",&k);
	sort(point+1,point+1+w,cmp2);
	
	for (int i = 0; i <= w; i++) C[i][0] = 1;
    for (ll i = 1; i <= w; i++) for (ll j = 1; j <= min(i, k); j++)
        C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        
	for(int i=1;i<=w;i++){
		if(i==1 || point[i].y!=point[i-1].y)cnt++;
		tmp[i] = cnt;
	}
	for(int i=1;i<=w;i++){
		point[i].y = tmp[i];
		num2[tmp[i]]++;//y 列 常青树的个数 
	}
	sort(point+1,point+1+w,cmp1);
	cnt = 0;
	for(int i=1;i<=w;i++){
		if(i==1 || point[i].x!=point[i-1].x)cnt++;
		tmp[i] = cnt; 
	}
	for(int i=1;i<=w;i++){
		point[i].x = tmp[i];
		num[tmp[i]]++;//x 行 常青树 的个数
	}
	ll ans = 0,col;//col 列向上 的个数 
	cnt = 0;
	for(int i=1;i<=w;i++){
		if(i==1 || point[i].x!=point[i-1].x)cnt = 0;
		col = point[i].y;
		ll v = ++h[col];
		v = v>=k && num2[col] - v >=k ? C[v][k]*C[num2[col] - v][k]%MOD : 0; cnt++;
		add(col,v-r[col]); r[col] = v;
		if(i==w || cnt <k || num[point[i].x] - cnt <k || point[i].x!=point[i+1].x || point[i+1].y - point[i].y <=1)
			continue;
		ans+= ( C[cnt][k]*C[num[ point[i].x ] - cnt][k]%MOD )*(sum(point[i+1].y - 1) - sum(point[i].y) )%MOD;
	}
	printf("%lld\n",(ans+MOD)%MOD);
	return 0; 
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据科学家节选(4)

    人们热衷于进行各种数据观测、拟合,希望对数据进行可期望的预判,这种行为究竟本质上是在做什么呢?从带有一定功利色彩的眼光来看,这实际上是一种趋利避害的过程。 在...

    刀刀老高
  • 达则兼妓天下,穷则独占妻身——论大数据教的起源

    本文的标题语,来自我的高中同学,现就职于阿里集团,擅长跳探戈的某非著名仁波切,在这里对他表示言不由衷的感谢。

    华章科技
  • 互联网创业的猴子理论

    前几天,一则“多家App因为刷榜被苹果下架”的新闻激起了我的表达欲,在我看来这则内容其实说了两点:第一,很多创业公司不顾风险,为了“榜单”和“流量”,冒着极大的...

    华章科技
  • 享知行·思考:不要再拜服务器啦,墨菲定律有空了解一下

    虔诚的膜拜机房真的有用吗?贴上一张“永不宕机”的神符,服务器真的就不会宕机吗?该宕机还是会宕机,只是概率大小的问题罢了。“得道高僧”就能永保平安?与其如此,不如...

    用户4361942
  • 阿斯汤加瑜伽学习笔记-唱诵经文

    祈祷式: for the beginning of Ashtanga Yoga practice

    Spaceack
  • [- Flutter 跨界篇-]昨晚简记+Flutter桌面、Web开发

    张风捷特烈
  • 消息提示框-事件冒泡

    ProsperLee
  • 使用Vmware虚拟机部署开发环境之Mac OS X系统安装

    一、使用VMware虚拟机部署Mac开发环境所需工具: Vmware Workstation 14.0虚拟机软件 VM安装Mac解锁工具Unlock 苹...

    企鹅号小编
  • 圣经中的校验码

    司马迁用近53万字记载了中国上千年的历史,远在中东的犹太人也用类似的篇幅记载了自创世纪以来他们祖先的历史。《圣经》简洁的文风和中国的《史记》颇有相似之处。但是和...

    Defu Li

扫码关注云+社区

领取腾讯云代金券