AtCoder AGC036F Square Constraints

题目大意

◇题目传送门◆

求有多少种$0$到$2N-1$的排列$p$，对于任意一个位置$i$总有$N^2\le {p_i}^2+i^2\le (2N{)}^2$。

分析

很容易想到把限制拆成${p_i}^2+i^2<N^2$和${p_i}^2+i^2\le 4N^2$。这样我们就可以求出分别满足两个限制的方案数，最后作差就是了。

但这样做似乎仍然不好算，那么我们考虑容斥，即将限制分解成至少有$k$个数满足${p_i}^2+i^2\le N^2-1$，且所有的数都满足${p_i}^2+i^2\le 4N^2$。

---

补充： 对于一个排列$p$，若我们已经知道了每个位置上的最大值$a_i$，由于我们必须从取值范围小的数开始算，那么这个排列的方案数就是：

$$\prod _{i=1}^N(a_i-i+1)$$

---

考虑如何计算这个限制的方案数。

设函数$f(i)$为满足$i^2+a^2\le 4N^2$的最大的$a$，$g(i)$为满足$i^2+a^2\le N^2$的最大的$a$。

不难证明$g(i)$只有$N$个，且两个函数都是单调递减的。

一个比较直观的想法是在前面$N$个位置中选出$k$个$g(i)$。这样就满足条件了。

根据定义，我们可以得到对于$f(i),N\le i<2N$，它必定是在排列中的。

那么剩下的$N$个位置，就有可能是$g(i)$或者$f(i)$了。

由于我们必须从小到大考虑每个位置，又因为任意一个$g(i)$一定比任意一个$f(i)$小，所以我们进行如下操作：

当$0\le i<N$时，我们将$f(i),g(i)$绑成二元组$(g(i),f(i))$；当$i\ge N$时，我们将$f(i)$绑成二元组$(f(i),0)$。

最后排序就可以了，这样我们就可以顺序考虑而不必一位一位地算了。而计算这个方案的方法，我们采用DP。

---

设状态$f(i,j)$表示在前$i$个位置上选出了$j$个$g(i)$的方案数。

考虑如何转移：

再定义两个辅助变量$c_1,c_2$，分别记录在前$i$个位置上二元组$(f(i),0)$的个数，$(g(i),f(i))$的个数。

对于第$i$个二元组，我们分成两种情况讨论：

若这个二元组是$(f(i),0)$，显然我们只能够选$f(i)$。 考虑它是第几大： 在它前面有$c_1$个$(f(i),0)$，由于排了序，这个$(f(i),0)$一定是最大的；又因为在它前面还有$j$个$(g(i),f(i))$，显然$f(i)$肯定比这$j$个$g(i)$大，所以这个$f(i)$是第$c_1+j$个考虑贡献： $f(i,j)$对$f(i+1,j)$的贡献为$f(i,j)\times (f(i)-c_1-cnt)$。 若这个二元组是$(g(i),f(i))$，那么我们有两种选法： 选$g(i)$： 由于有不超过$k$个的限制，这种选法只能够在$j<k$时成立（因为我用的是刷表法） 考虑排名： 在它之前有$c_1$个$f(i)$比它小，又有$j$个$g(i)$比它小，所以它的排名是$c_1+j$；考虑贡献： $f(i,j)$对$f(i+1,j+1)$的贡献为$f(i,j)\times (g(i)-c_1-j)$。 选$f(i)$： 考虑排名： 显然有$i<N$，又由于有$N$个$f(i)$是$i\ge N$且$f(i)$是单调递减的，那么我们可以知道这$N$个$f(i)$一定是在我们选的这个$f(i)$的前面的。又因为任意一个$f(i)$都大于$g(i)$，所以我们选出的$k$个$g(i)$都比$f(i)$要小，又由于之前还有$c_2-j$个$f(i)$，所以它的排名为$N+k+(c_2-j)$。考虑贡献： $f(i,j)$对$f(i+1,j)$的贡献为$f(i,j)\times \left[f(i)-N-k-(c_2-j)\right]$。

综上，我们可以算出$f(2N,k)$的结果，即有$k$个位置满足${p_i}^2+i^2<N^2$且所有位置均满足${p_i}^2+i^2\le 4N^2$的方案数，最后容斥一下就可以了。

参考代码

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int Maxn = 500; int N, Mod; vector<pair<int, int> > p; ll f[Maxn + 5][Maxn + 5]; inline int F(int i) { static int ret = 2 * N - 1; while(ret >= 0 && i * i + ret * ret > 4 * N * N) ret--; return ret + 1; } inline int G(int i) { static int ret = 2 * N - 1; while(ret >= 0 && i * i + ret * ret >= N * N) ret--; return ret + 1; } int main() { #ifdef LOACL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif scanf("%d %d", &N, &Mod); for(int i = 0; i <= 2 * N - 1; i++) { if(i < N) p.push_back(make_pair(G(i), F(i))); else p.push_back(make_pair(F(i), 0)); } sort(p.begin(), p.end()); ll ans = 0; for(int k = 0; k <= N; k++) { memset(f, 0, sizeof f); f[0][0] = 1; int cnt1 = 0, cnt2 = 0; for(int i = 0; i < (int)p.size(); i++) { for(int j = 0; j <= k; j++) if(p[i].second == 0) { f[i + 1][j] = (f[i + 1][j] + f[i][j] * (p[i].first - j - cnt1) % Mod) % Mod; } else { if(j < k) f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * (p[i].first - j - cnt1) % Mod) % Mod; f[i + 1][j] = (f[i + 1][j] + f[i][j] * (p[i].second - N - k - (cnt2 - j)) % Mod) % Mod; } if(p[i].second == 0) cnt1++; else cnt2++; } if(k % 2) ans = (ans - f[p.size()][k] + Mod) % Mod; else ans = (ans + f[p.size()][k]) % Mod; } printf("%lld\n", ans); return 0; }