上午跟同学讨论的结果是认为可以容斥，但是没想到比较好的做法
by 半只蒟蒻 @ 2024-03-19 23:53:34
$A_i$ 指的是第 $i$ 个学生不喜欢的学号
by 半只蒟蒻 @ 2024-03-19 23:54:32
@[半只蒟蒻](/user/112049) 确实是容斥，考虑给每个人要不要钦定它必须分到 $a_i$，假设钦定了 $k$ 个人，应当要满足这些人的 $a$ 互不相同，方案数是给剩下人随便分的 $(n-k)!$ 乘上容斥系数 $(-1)^k$
处理 $a$ 互不相同的限制，直接算出 $c_i$ 表示 $a$ 中有多少 $i$，每次要么是不钦定 $a=i$ 的任何一个人，要么选一个 $a=i$ 的人钦定。可以 DP 设 $f_j$ 表示钦定了 $j$ 个人的系数和，容易转移
by chenxinyang2006 @ 2024-03-20 00:02:56
@[半只蒟蒻](/user/112049) 根据上面那个老哥，我们只需要计算 $f(x)=(1+c_1x)(1+c_2x)\dots(1+c_nx)$。
直接 NTT 是 $\mathcal O(n\log^2 n)$ 的。
注意到这里 $\sum c_i=n$，我们可以把所有的 $c_i$ 再统一遍变成 $\prod (1+ix)^{d_i}$ 的形式。这样子，$(1+ix)^{d_i}$ 可以二项式展开。之后我们可以直接进行分治 NTT，每次只卷最小的两个，这样子复杂度是 $\mathcal O(n\log n)$ 的。
by Inaba_Meguru @ 2024-03-20 01:04:34
@[半只蒟蒻](/user/112049) @[chenxinyang2006](/user/49776) @[Inaba_Meguru](/user/248400)
我们考虑每个学号 $i$ 是多少人不喜欢的，将这个数量记为 $c_i$。设 $S$ 是**确定被分配到的**不被喜欢的学号集，则它对答案的贡献是
$$(-1)^{|S|} \left( \prod_{i \in S}c_i\right)(n-|S|)!$$
（$S$ 中每个学号随便选一个人分配，剩下的随便排列）
所以设多项式
$$f(x)=\prod_{i=0}^{n-1}(1+c_i x)$$
答案即为：
$$\sum_{i=0}^n([x^i] f(x)) (-1)^i(n-i)!$$
关于计算的时间复杂度，由于 $c_i$ 之和为 $n$，可以使用 [此题解](https://www.luogu.com.cn/article/k1ldr92u) 的做法，达到 $\Theta(n)$ 的时间复杂度。实际上，若设
$$g(x)=\prod_{i=0}^{n-1}(x-c_i)$$
就可以发现这两题是本质相同的。
by NaCly_Fish @ 2024-03-20 08:45:21
这题让我想到了 https://www.luogu.com.cn/problem/P6870
by 寒烟冷浅暮殇 @ 2024-03-20 10:33:43
@[chenxinyang2006](/user/49776) @[Inaba_Meguru](/user/248400) @[NaCly_Fish](/user/115864) 好的，谢谢
by 半只蒟蒻 @ 2024-03-20 14:07:44