CVBB ACM Team

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


====== 个人总结 ======
===== 陈铭煊 Max.D. =====
这周还是很忙，暂无进一步的学习记录。


===== 龙鹏宇 Hardict =====


===== 肖思炀 MountVoom =====

这个人还没从计网实验中活过来

====== 本周推荐 ======
===== 陈铭煊 Max.D. =====

推荐这样一道题：https:%%//%%ac.nowcoder.com/acm/contest/5633/D

题意是给出一个序列$a$，求多少组排列$p$满足对任意的$i$，有$p[i]\neq a[i]$。

我们容易知道当$a[i]=i$时求的就是错排数，如果是其他情况呢？

这里用到容斥原理+动态规划，状态的设置我觉得是极其巧妙的：

用$g(x)$代表选出$x$个取值，每个取值数字被不合法的$p[i]$所映射的情况数。

设$f(x)=x!$，那么$g(x)\times f(n-x)$为至少$x$个取值存在被不合法映射的方案数。

根据**容斥原理**答案为： $$
\sum_{i=0}^{n}(-1)^{i} * g(x) * f(n-x)
$$ 设$h_i$表示不可以映射到$i$的$p$的位置个数，初始时： $$
g(0)=1, g(k)=0(k>1)
$$ 然后定义$dp$状态为考虑前$i$个值，选出$x$个取值，每个取值数字被不合法的$p[i]$所映射的情况数。那么$g(x)=dp[n][x]$。而$dp[i][x]=dp[i-1][x]+dp[i-1][x-1]*h[i]$。因此可以求出所有$g(i)$最后统计答案。时间复杂度是$O(n^2)$的。

===== 龙鹏宇 Hardict =====

===== 肖思炀 MountVoom =====
无

CVBB ACM Team

用户工具

站点工具

页面工具