菜王的 blog

由于某些原因，文中所有的“钦定”都被替换成了“按住”。

题目中的合法条件显然等价于，存在一个序列的分界点，使得分界点左边存在至少一个 $i$ 个大小为 $A$ 的置换环，右边存在至少一个大小为 $B$ 的置换环，“存在”“至少”这些词汇自然将我们导向容斥。

考虑对于一个合法分界点，强制按住左边有 $i$ 个大小为 $A$ 的置换环，右边有 $j$ 个大小为 $B$ 的置换环（显然需要使得 $i, j > 0$）。那么这样做的容斥系数则为 $(-1)^{i - 1}(-1)^{j - 1}$，也就是 $(-1)^{i + j}$。

那么我们观察到，对于一个排列，它的合法分界点显然是一个区间，所以我们可以使用点边容斥，但是这样时间复杂度里会多出来一个 $n$。

实际上我们并不关心分界点具体位于哪里，所以先确定好这 $i + j$ 个置换环的形态，再将剩余的数归并进来就可以直接省掉这个枚举分界点具体位置的过程。

设 $f_i$ 表示长为 $i \times A$ 的排列恰好形成 $i$ 个大小为 $A$ 的置换环的方案数，$g_i$ 表示长为 $i \times B$ 的排列恰好形成 $i$ 个大小为 $B$ 的置换环的方案数，那么我们可以列出答案式子：

$\sum_{i = 1}^{n / A} \sum_{j = 1}^{n / B} (-1)^{i + j} \frac{n!}{(iA + jB)!} f_i g_j$

暴力计算时间复杂度为 $\mathcal{O}(\frac{n^2}{AB})$。这个东西显然是可以写成卷积形式的，所以可以简单做到 $\mathcal{O}(n \log n)$。

顺带一提，如果你不会 NTT 但是又不想只拿 $77$ 分（但是场上好像也没人有 $77$），由于当 $B = 1$ 时有所有的 $g_i = 1$，所以我们只需要对阶乘的倒数做前缀和，就可以 $\mathcal{O}(n)$ 做这个性质了，成功在不使用十级算法的基础上获得 $97$ 分（$A = 1$ 也是同理）。

代码删去了多项式类以及 modint 类。

// 全身全霊！MORE MORE JUMP!!
const int N = 1000005;poly f, g;
int n, A, B;mint fac[N], ifc[N], ans;
int main(){cin >> n >> A >> B, f.resize(n + 1), g.resize(n + 1);
	fac[0] = ifc[0] = f[0] = g[0] = 1;
	for (int i = 1;i <= n;i ++) fac[i] = fac[i - 1] * i, ifc[i] = ifc[i - 1] / i;
	for (int i = A;i <= n;i += A) f[i] = f[i - A] * fac[i - 1] * ifc[i - A];
	for (int i = A;i <= n;i += A + A) f[i] = -f[i];
	for (int i = B;i <= n;i += B) g[i] = g[i - B] * fac[i - 1] * ifc[i - B];
	for (int i = B;i <= n;i += B + B) g[i] = -g[i];
	f[0] = g[0] = 0, f = f * g;
	for (int i = 1;i <= n;i ++) ans += f[i] * ifc[i];
	ans *= fac[n], cout << ans;
}