【AtCoder】【容斥】AGC036F-Square Constraints

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 LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%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;
}