题解：AT_agc036_f [AGC036F] Square Constraints
liaoz123
·
·
题解
从 CSP-S2025 第四题的容斥做法过来的。
同时我们注意到，随着 $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;
}
```