2020-2021:teams:alchemist:weekly_digest_5
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:alchemist:weekly_digest_5 [2020/06/06 23:24] maxdumbledore |
2020-2021:teams:alchemist:weekly_digest_5 [2020/06/06 23:40] (当前版本) maxdumbledore [陈铭煊 Max.D.] |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| ===== 陈铭煊 Max.D. ===== | ===== 陈铭煊 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 ===== | ===== 龙鹏宇 Hardict ===== | ||
2020-2021/teams/alchemist/weekly_digest_5.1591457083.txt.gz · 最后更改: 2020/06/06 23:24 由 maxdumbledore
