「AGC036F」Square Constraints 题解
题目大意
给定一个整数 $ n $，求有多少种 $ 0\ -\ 2n!-!1 $ 的排列 $ P $，使得对于每个 $ i $，都有 $ n^2 \le i^2 + P_i^2 \le 4n^2 $。输出答案对给定的 $ m $ 取余的结果。
输入
两个整数，$ n \(，\) m $。
输出
一个整数，表示答案。
思路
初始想法
通过 $ n^2 \le i^2 + P_i^2 \le 4n^2 $ 这个式子，我们很容易想到用 $ i^2 + P_i^2 \le 4n^2 $ 的方案数减去 $ i^2 + P_i^2 < n^2 $ 的方案数。但是我们发现实际上不可做。不过这种想法提示我们可以考虑容斥。
深入思考
首先，我们提炼一下问题模型：
- 对于一个 $ 0\ -\ 2n-1 $ 组成的序列 $ P $，限制 $ a_i \le P_i \le b_i $，求方案数。
我们考虑这个问题的弱化版：
- 对于一个 $ 0\ -\ 2n-1 $ 组成的序列 $ P $，限制 $ P_i \le a_i $，求方案数。
我们考虑将 $ a $ 数组从小到大排序，那么这个弱化版的答案为：
\[\underset{i=0}{\overset{2n-1}{\prod}}a_i-i \]证明：
首先将 $ a $ 数组从小到大排序。
对于这个排列 $ P $，我们肯定先从 $ a $ 小的开始放。所以第一步的方案数为 $ a_0 $ 。
再考虑下一个数 $ 1 $。此时剩下 $ 2n-1 $ 个数。因为 $ a $ 从小到大，所以上一轮选走的数一定小于等于 $ a_1 $。此时的方案数为 $ a_1-1 $。
因为这些步骤是递进的，所以方案数是每一步的方案数的乘积。最终方案数即为：
\[a_0 \times (a_1-1) \times (a_2-2) \times \dots \times (a_{2n-1}-2n+1)\\ =\underset{i=0}{\overset{2n-1}{\prod}}a_i-i \]证毕。
而原问题模型多了一个限制条件，不难想到将满足两个条件的最大值都设出来，综合在一起，套用公式得到答案。
回到本题，我们将满足条件的最大值设出来。
我们尝试设 $ F(i) $ 为满足 $ i^2 + P_i^2 \le 4n^2 $ 的 $ P_i $ 的最大值， $ G(i) $ 为满足 $ i^2 + P_i^2 < n^2 $ 的 $ P_i $ 的最大值。其中 $ i \in [0,2n-1] $。
通过观察我们不难发现：
-
$ F $ 和 $ G $ 两个函数值随着 $ i $ 的增大而减小。
$ n^2 $ 和 $ i^2 $ 为定值，$ i $ 增大，则 $ i^2 $ 增大，那么 $ P_i^2 $ 就会减小。
-
$ G(i) $ 满足 $ i \in [0,n-1] $。
当 $ i \ge n $ 时，$ i^2 \ge n^2 $，要使 $ i^2 + P_i^2 < n^2 $，则 $ P_i^2 < 0 $，无解。
-
$ \max_{i=0}^{n-1}(G_i) < \min_{i=0}^{n-1}(F_i) $。
由于第一条规律：$ \max_{i=0}^{n-1}(G_i) $ 即 $ G_0 \(，\) \min_{i=0}^{n-1}(F_i) $ 即 $ F_{n-1} $，
$ \because 0^2 + G_0^2 < n^2 , n^2 + F_{n-1}^2 \le 4n^2 $
$ \therefore G_0^2 < n^2 , F_{n-1}^2 \le 3n^2 $
$ \because n^2 \le 3n^2 $
$ \therefore G_0^2 < F_{n-1}^2 \le 3n^2 $
$ \because G_0 \in \mathbb{N} ,F_{n-1} \in \mathbb{N} $
$ \therefore G_0 < F_{n-1} $
$ \therefore \max_{i=0}^{n-1}(G_i) < \min_{i=0}^{n-1}(F_i) $
有了这些东西，我们就可以将限制拆分为：
所有的数都满足 $ i^2 + P_i^2 \le 4n^2 $，且至少有 $ k $ 个数满足 $ i^2 + P_i^2 < n^2 $，也就是说在前面 $ n $ 个位置选出 $ k $ 个 $ G(x) $ 。
然后就可以进行容斥了。
什么？你不会容斥？你可以翻到最下面的补充知识。
在弱化版中，我们将 $ a $ 数组从小到大进行了排序。
所以我们类比一下，考虑将 $ F $ 和 $ G $ 两个函数打包成二元组排序。由于第三条规律，我们通过如下方式打包成二元组：
-
$ i \in [0,n-1] : (G(i),F(i)) $
-
$ i \in [n,2n-1] : (F(i),0) $
接下来按第一关键字进行排序。
接下来就是求解方案数。我们可以使用 $ DP $ 求解。
设 $ f_{i,j} $ 表示在前 $ i $ 个位置上选出了 $ j $ 个 $ G(x) $ 的方案数。
在状态转移时需要用到当前数在选出的位置上的排名，所以用两个变量 $ t1 $ 和 $ t2 $，分别统计前面 $ (F(x),0) $ 和 $ (G(x),F(x)) $ 的个数。
首先枚举 $ k $，从 $ 0 $ 到 $ n $，表示在前面 $ n $ 个位置选出 $ k $ 个 $ G(x) $；
然后枚举 $ i $，从 $ 0 $ 到 $ 2n-1 $，表示已经确定了前面 $ i $ 个位置；
最后枚举 $ j $，从 $ 0 $ 到 $ k $，表示前面已经选出了 $ j $ 个 $ G(x) $；
状态转移分情况讨论：
-
当前二元组是 $ (F(i),0) $：
-
选择 $ F(i) $：
- 排名：
前面选出的 $ j $ 个 $ G(x) $ 一定比 $ F(i) $ 小；
又因为排了序，前面的 $ t1 $ 个 $ F(x) $ 肯定也比 $ F(i) $ 小。
所以总共有 $ j+t1 $ 个数比 $ F(i) $ 小。
- 转移：
$ f_{i+1,j}=f_{i+1,j}+f_{i,j} \times (F(i)-j-t1) $
-
-
当前二元组是 $ (G(i),F(i)) $：
-
选择 $ F(i) $：
- 排名：
由于函数单调递减，所以 $ n $ 个二元组 $ (F(x),0)\ (x \in [n,2n-1]) $ 相对 $ F(i) $ 一定排在前面；
我们选出的所有 $ k $ 个 $ G(x) $ 都比 $ F(i) $ 小；
之前 $ (G(x),F(x)) $ 类型的二元组选出的 $ t2-j $ 个 $ F(x) $ 也都比 $ F(i) $ 小。
所以总共就有 $ n+k+t2-j $ 个数比 $ F(i) $ 小。
- 转移：
$ f_{i+1,j}=f_{i+1,j}+f_{i,j} \times (F(i)-n-k-t2+j) $
-
选择 $ G(i) $：（注意只能选 $ k $ 个）
- 排名：
前面选出的 $ t1 $ 个 $ F(x) $ 一定比 $ G(i) $ 小；
前面选出的 $ j $ 个 $ G(x) $ 也比 $ G(i) $ 小；
总共就有 $ t1+j $ 个数比 $ G(i) $ 小。
- 转移：
$ f_{i+1,j+1}=f_{i+1,j+1}+f_{i,j} \times (G(i)-t1-j) $
-
最后综合起来求出 $ f_{2n-1,k} $，容斥即可。
代码实现
#include<bits/stdc++.h>
#define ll long long
const ll N=501;
using namespace std;
ll n,p;
ll f[N][N];
vector<pair<ll,ll>>t;//记录二元组
ll F(ll i){//F函数
ll ans=2*n-1;
while(ans>=0&&i*i+ans*ans>4*n*n)ans--;//注意是大于
return ans+1;
}
ll G(ll i){//G函数
ll ans=2*n-1;
while(ans>=0&&i*i+ans*ans>=n*n)ans--;//注意是大于等于
return ans+1;
}
int main(){
scanf("%lld%lld",&n,&p);
for(ll i=0;i<2*n;i++){//预处理二元组
if(i<n)t.push_back({G(i),F(i)});
else t.push_back({F(i),0});
}
sort(t.begin(),t.end());//对二元组按第一关键字排序
ll ans=0;
for(ll k=0;k<=n;k++){
//初始化
memset(f,0,sizeof(f));
f[0][0]=1;
ll t1=0,t2=0;//辅助统计变量
for(ll i=0;i<t.size();i++){
for(ll j=0;j<=k;j++){
if(!t[i].second){//(F(i),0)
f[i+1][j]=(f[i+1][j]+f[i][j]*(t[i].first-j-t1)%p)%p;//选F(i)
}else{//(G(i),F(i))
if(j<k){//选了之后不能超过k个
f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(t[i].first-j-t1)%p)%p;//选G(i)
}
f[i+1][j]=(f[i+1][j]+f[i][j]*(t[i].second-n-k-t2+j)%p)%p;//选F(i)
}
}
if(!t[i].second)t1++;
else t2++;
}
//容斥
if(k%2)ans=(ans-f[t.size()][k]+p)%p;
else ans=(ans+f[t.size()][k])%p;
}
printf("%lld",ans);
return 0;
}
补充知识
容斥原理
容斥原理是一种组合数学常用的方法。
比如说，你要计算几个集合并集的大小，我们可以先将所有单个集合的大小加起来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分……依此类推，最终你就可以得出答案。
用数学公式可以表示为：
\[\left | \bigcup_{i=1}^{n}a_i \right | = \underset{T \subseteq \{1,2,...,n\}}{\sum}(-1)^{|T|-1} \left | \bigcap_{i \in T} a_i \right | \]广义容斥原理
容斥原理求的是不满足任何性质的方案数，我们通过计算所有至少满足 $ k $ 个性质的方案数之和来计算。
同样的，我们可以通过计算所有至少满足 $ k $ 个性质的方案数之和来计算恰好满足 $ k $ 个性质的方案数。这样的容斥方法我们称之为广义容斥原理。
一般我们会用二项式反演进行计算。
二项式反演
对于函数 $ f(k) $ 和 $ g(k) $，满足：
\[g(k) = \underset{i=0}{\overset{k}{\sum}} C_k^i f(i) \]则：
\[f(k) = \underset{i=0}{\overset{k}{\sum}} (-1)^{k-i} C_k^i g(i) \]它一般用于"恰好"和"至少""至多"的转换式中。
举个例子：
「bzoj2839」集合计数
一个有 $ n $ 个元素的集合有 $ 2^n $ 个不同子集（包含空集），现在要在这 $ 2^n $ 个集合中取出至少一个集合，使得它们的交集的元素个数为 $ k $ ，求取法的方案数模 $ 10^9+7 $。
$ 1 \le n \le 10^6 \(，\) 0 \le k \le n $。
由题列出式子：$ C_n^k (2{2{n-k}}-1) $。即钦定 $ k $ 个交集元素，则包含这 $ k $ 个的集合有 $ 2^{n−k} $ 个；每个集合可选可不选，但不能都不选。
设 $ f(i) $ 表示钦定交集元素为至少 $ i $ 个的方案数，$ g(i) $ 表示钦定交集元素恰好为 $ i $ 个的方案数，则有 $ C_n^k (2{2{n-k}}-1) = f(k) = \underset{i = k}{\overset{n}{\sum}} C_i^k g(i) $。
这个时候我们就可以利用二项式反演，求得 $ g(k) = \underset{i = k}{\overset{n}{\sum}} (-1)^{i-k} C_i^k f(i) = \underset{i=k}{\overset{n}{\sum}} (-1)^{i-k} C_i^k C_n^i (2{2{n-i}}-1) $。
这样就可以 $ O(n) $ 求出答案。
尾声
如果你发现了问题，你可以直接回复这篇题解
如果你有更好的想法，也可以直接回复！
标签：方案,Square,题解,ll,容斥,le,ans,2n,Constraints From： https://www.cnblogs.com/zsc985246/p/16621307.html