CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 团队 =====

做毕设，摸了。

===== 个人 =====

==== zzh ====

[[https://codeforces.com/contest/1358/|Codeforces Round #645 (Div. 2)]]: ''pro: 5/6/6'' ''rk: 80/18169''

[[https://codeforces.com/contest/1359/|Educational Codeforces Round 88]]: ''pro: 5/6/6'' ''rk: 159/14430''

学习了一下 SA。

==== pmxm ====


本周没有打比赛
==== jsh ====

===== 本周推荐 =====

==== zzh ====

Python：众所周知，Python 的整数是无限精度的，很多同学也可能知道 Python 有 decimal 处理浮点数。不过可能知道 Fraction 的人就不那么多了。例如 [[https://codeforces.com/contest/1359/problem/C|Educational Codeforces Round 88 C]] 这样的题，如果用 C++ 写可能会累死累活写 20 分钟，甚至还容易写错。而使用 Python 则可以很容易完成。

==== pmxm ====

KM如何保持复杂度和点数少的那一边一致的问题。

一个online问题:

在线二分图匹配问题，给定一个二分图，每条边会在线的加入和删除，求最大匹配。
==== jsh ====

=== 错排问题（错位排列） ===

错排，是个时常会听到，但做到就有点抓瞎的东西。

原始的全错位排列问题的做法有很多种，但要记得了解到做法的本质，因为出题通常就是某种做法的本质没变，在条件上稍加改动而已。

具体的可参考 [[https://zh.wikipedia.org/zh-cn/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98|错排问题 - 维基百科]] 和 [[https://baike.baidu.com/item/%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F|错排公式 - 百度百科]]。

== 牛客练习赛64 - D - 宝石装箱 ==

[[https://ac.nowcoder.com/acm/contest/5633/D|题目链接]]

题意：

共 $n$ 个编号的宝石和 $n$ 个编号的箱子，$n \le 8000$。每个箱子要装有恰好一个宝石，但第 $i$ 个宝石不能放在第 $a_i$ 个箱子里。

问有多少种装箱的方案数。取模。

$a_i$ 不是个排列，可能有重。


<hidden 题解>
错排改了改，每个物品的限制虽然还是一个，但限制可能有重复。

范围上看 $\mathcal{O}(n^2)$ 就能过。

那我们考虑一下容斥，记 $A_i$ 为每个箱子要装有恰好一个宝石的情况下，第 $i$ 个宝石放在了第 $a_i$ 个箱子的方案集合，方案数就是：
\[{\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|}\]

哦天哪，我们把所有 $j$ 个 $A_i$ 的交集的大小的和，记为 $S_j$，即有 $j$ 个宝石放错，其余随便放的方案数。问题的答案就是：
\[\sum_{i=0}^{n} (-1)^i S_i\]

这个 $S_j$ 很好算。记第 $i$ 个箱子有 $b_i$ 个宝石不能放，那么对于放错宝石的数量贡献与否，可以得到多项式：
\[\prod_{i} (1 + b_i x)\]

记展开的第 $i$ 项系数为 $c_i$，即 $i$ 个宝石放错的玩法。我们乘上其余宝石乱排的方案数，有 $S_i = c_i (n - i)!$。

那个多项式展开就是个背包，$\mathcal{O}(n^2)$ DP 一下，剩下的都好做。

zzh's comment：多嘴一下，FFT 甚至可以做到 $\mathcal{O}(n\log^{2}n)$。
</hidden>
CVBB ACM Team

用户工具

站点工具

页面工具
