题解：P9563 [SDCPC 2023] Be Careful 2

不考虑容斥，从上往下扫描线。

将所有点按照横坐标排序，从大到小加入每个点，每次只统计下边界横坐标在

[x_{i-1},x_i)

的所有正方形，考虑其上边界所在的位置。

先将加入的所有点按

y

排序（可以插入排序）。画图发现有两种情况：

对一个点 $(x_i,y_i)$ ，单调栈求出每个点左边第一个 $x<x_i$ 的点（设为 $(x_j,y_j)$ ）、右边第一个 $x<x_i$ 的点（设为 $(x_k,y_k)$ ），上边界在 $\max(x_j,x_k)+1\le x\le x_i,y_j\le y\le y_k$ 这样一个矩形中（注意不要算重）；
考虑相邻两个点 $(x_i,y_i),(x_{i+1},y_{i+1})$ ，若 $y_i<y_{i+1}$ ，则上边界在 $\max(x_i,x_{i+1})+1\le x\le n,y_i\le y\le y_{i+1}$ 这样一个矩形中。

转化为求解

f(n,m,d,u)

：

n\times m

的矩形内，上边界横坐标在

[u,m]

，下边界横坐标在

[0,d]

的正方形个数。

简单容斥一下：设

g(n,m)

表示

n\times m

的矩形内的正方形个数，

f(n,m,d,u)=g(n,m)-g(u-1,m)-g(n-d-1,m)+g(u-d-2,m)

。而

g(n,m)

是好求的：

g(n,m)=\sum_{d=1}^{\min(n,m)}(n-d+1)(m-d+1)d^2

是一个四次多项式前缀和的形式，拆成平方和、三次方和、四次方和即可。放一下比较冷门的四次方和公式：

\sum_{i=1}^ni^4=\dfrac{n^5}5+\dfrac{n^4}2+\dfrac{n^3}3-\dfrac{n}{30}

复杂度

O(k^2)

。代码实现略有不同。

CPP

#include<bits/stdc++.h>
#define N 5005
#define ll long long
#define mod 998244353
#define inv2 499122177
#define inv3 332748118
#define inv5 598946612
#define inv6 166374059
using namespace std;
int n,m,k;
struct point{
	int x,y;
}a[N];
bool cmpx(point a,point b){
	return a.x<b.x;
}
bool cmpy(point a,point b){
	return a.y<b.y||a.y==b.y&&a.x<b.x;
}
ll qmi(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod) if(b&1) ans=ans*a%mod;
	return ans;
}
ll S1(ll n){
	return n*(n+1)%mod*inv2%mod;
}
ll S2(ll n){
	return n*(n+1)%mod*(n*2+1)%mod*inv6%mod;
}
ll S3(ll n){
	return S1(n)*S1(n)%mod;
}
ll S4(ll n){
	return (qmi(n,5)*inv5%mod+qmi(n,4)*inv2%mod+qmi(n,3)*inv3%mod-n*inv6%mod*inv5%mod+mod)%mod;
}
ll calc0(ll a2,ll a3,ll a4,ll n){
	return (a2*S2(n)+a3*S3(n)+a4*S4(n))%mod;
}
ll calc1(int n,int m){
	if(n<=0||m<=0) return 0;
	return calc0((ll)(n+1)*(m+1)%mod,(mod-(n+m+2)%mod)%mod,1,min(n,m));
}
ll calc2(int n,int m,int d,int u){
	if(n<=0||m<=0||u-d>m||u>n) return 0;
	return ((calc1(n,m)-calc1(u-1,m)-calc1(n-d-1,m)+calc1(u-d-2,m))%mod+mod)%mod;
}
ll ans;
int st[N],top;
int pl[N],pr[N],d[N],tag[N];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++) scanf("%d%d",&a[i].x,&a[i].y);
	sort(a+1,a+k+1,cmpx);
	ans=calc1(n-a[k].x,m);
	for(int i=k;i>=1;i--){
		if(a[i].x==a[i-1].x) continue;
		int d1=a[i-1].x,d2=a[i].x-1-a[i-1].x;
		sort(a+i,a+k+1,cmpy);
		top=0;
		for(int j=i;j<=k;j++){
			tag[j]=0,d[j]=d1;
			while(top&&a[st[top]].x>a[j].x) top--;
			if(top&&a[st[top]].x==a[j].x) tag[j]=1,top--;
			if(top) pl[j]=a[st[top]].y,d[j]=max(d[j],a[st[top]].x);
			else pl[j]=0;
			st[++top]=j;
		}
		top=0;
		for(int j=k;j>=i;j--){
			while(top&&a[st[top]].x>=a[j].x) top--;
			if(top) pr[j]=a[st[top]].y,d[j]=max(d[j],a[st[top]].x);
			else pr[j]=m;
			st[++top]=j;	
		}
		for(int j=i;j<=k;j++){
			if(tag[j]) continue;
			ans=(ans+calc2(a[j].x-d1,pr[j]-pl[j],d2,d[j]+1-d1));
		}
		ans=(ans+calc2(n-d1,a[i].y,d2,a[i].x+1-d1))%mod;
		ans=(ans+calc2(n-d1,m-a[k].y,d2,a[k].x+1-d1))%mod;
		for(int j=i;j<k;j++) ans=(ans+calc2(n-d1,a[j+1].y-a[j].y,d2,max(a[j+1].x,a[j].x)+1-d1))%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

题解：P9563 [SDCPC 2023] Be Careful 2

文章操作

相关推荐

评论

题解：P9563 [SDCPC 2023] Be Careful 2