题解：AT_agc036_f [AGC036F] Square Constraints

从 CSP-S2025 第四题的容斥做法过来的。

i^2+p_i^2

联想到线段长的平方，那么两边的限制在二维平面上围成了一个同心圆，外圆半径为

2n

，内圆半径为

n

。那么

(i,p_i)

就应该位于这个同心圆内部，可以得到

p_i

的范围

[l_i,r_i]

。注意下标从

0

开始。

同时我们注意到，随着

i

的增加，

p_i

的范围区间是单调的。并且当

i\in[n,2n)

时，

l_i=0

，当

i\in[0,n)

时，

l_i>0

。

如果每个

p_i

的下界

l_i

都是

0

，那么我们将所有

r_i

排序后，答案就是

\prod(r_i-i+1)

。

如果存在下界，那么刚才的办法就行不通，因为我们无法得知当前的数有多少种选择方案。因此我们考虑对 $l_i$ 非零的 $i$ 容斥，将

[l_i,r_i]

容斥为

[0,r_i]

的方案减去

[0,l_i-1]

的方案。假设我们算出了选择了

k

个

i

并容斥他们的范围为

[0,l_i-1]

的方案数

f_k

，那么他会对答案造成

(-1)^kf_k

的贡献。

然而就算我们进行了容斥，由于一个

i

需要考虑

[0,r_i]

和

[0,l_i-1]

两种情况，我们不便在 dp 时准确地得知每个位置可以填的数的方案数。但是……这真的不能做到吗？

为了实现这一点，我们考虑更换排序方式，对于

l_i=0

的

i

，他们不需要容斥，将他们的

r

作为关键字，对于

l_i>0

的，需要考虑容斥，将他们的

l-1

作为第一关键字，

r

作为第二关键字，两种情况放到一起排序。然后我们设

f_{i,j}

表示考虑了排序后的前

i

个数，选择了

j

个数使他们的范围变为

[0,l-1]

的方案数。

那么考虑加入第

i+1

个数，设之前有

x

个

l_i=0

的数，有

y

个

l_i>0

的数，分三种情况：

\bullet

若

l_{i+1}=0

，则

f_{i,j}\times(r_{i+1}+1-j-x)\to f_{i+1,j}

，当前数的可选择的数为

\le r_{i+1}

的

r_{i+1}+1

个数，减去前面选择的

j

个范围为

[0,l-1]

的数（他们排完序以后，一定有

l_p-1\le r_{i+1}

），再减去前面其他的

l=0

的数。

\bullet

若

l_{i+1}>0

，并选择他的范围为

[0,l_{i+1}-1]

，则

f_{i,j}\times (l_{i+1}-j-x)\to f_{i+1,j+1}

，选择方案数同上一种情况分析。

\bullet

若

l_{i+1}>0

，并选择他的范围为

[0,r_{i+1}]

，则

f_{i,j}\times (r_{i+1}+1-n-k-(y-j))\to f_{i+1,j}

，这种情况的选择方案数，包括

\le r_{i+1}

的

r_{i+1}+1

个数，减去

l=0

的

n

个数，减去全局选择了范围为

[0,l-1]

的

k

个数，再减去前面

l>0

但选择了范围为

[0,r]

的

y-j

个数。由于

l>0

的数的

r

一定满足

r\ge\sqrt 3n>lmax

，所以只有后面

l=0

的且选择了范围为

[0,r]

数不会占用当前数的选择方案。

一次转移是

O(n^2)

的，由于第三种情况方案数计算时需要一个确定的

k

，所以我们需要在最外层再枚举选择范围为

[0,l-1]

的个数

k

，总复杂度为

O(n^3)

。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500+5;
int n;ll mod,f[N][N],ss;
struct node{
	int l,r;
	bool operator <(const node x)const{
		if(!l&&!x.l)return r<x.r;
		if(!l)return r==x.l-1?l<x.r:r<x.l-1;
		if(!x.l)return l-1==x.r?r<x.l-1:l-1<x.r;
		else return x.l==l?r<x.r:l<x.l;
	}
}a[N];
int main(){
	scanf("%d%lld",&n,&mod);
	for(int i=0;i<n*2;i++){
		if(i<n)a[i+1].l=ceil(sqrt(n*n-i*i));
		a[i+1].r=min(int(floor(sqrt(4*n*n-i*i))),2*n-1);
	}
	sort(a+1,a+2*n+1);
	for(int k=0;k<=n;k++){
		memset(f,0,sizeof(f));f[0][0]=1;
		int ca=0,cb=0;
		for(int i=1;i<=n*2;i++){
			for(int j=0;j<=cb;j++){
				if(!f[i-1][j])continue;
				if(a[i].l){
					f[i][j]=(f[i][j]+f[i-1][j]*(a[i].r+1-k-n-(cb-j)))%mod;
					if(j!=k)f[i][j+1]=(f[i][j+1]+f[i-1][j]*(a[i].l-j-ca))%mod;
				}
				else f[i][j]=(f[i][j]+(a[i].r+1-ca-j)*f[i-1][j])%mod;
			}
			if(a[i].l)cb++;else ca++;
		}
		if(k&1)ss=(ss-f[2*n][k]+mod)%mod;
		else ss=(ss+f[2*n][k])%mod;
	}
	cout<<ss<<endl;
	return 0;
}

题解：AT_agc036_f [AGC036F] Square Constraints

文章操作

相关推荐

评论

题解：AT_agc036_f [AGC036F] Square Constraints