Contest: AtCoder Beginner Contest 226

tony102

2021 年 11 月 11 日

1700 次浏览

暂无评论

1301字数

总结比赛记录

智障手抽人快速幂写错导致最后 1min 没有冲出 F

不过是我太菜了

## A

不解释

不懂为什么 `printf("%.0lf", a)` 会 WA 最后一个点

吃了两发罚时，吐血了

## B

不解释

## C

还是不懂为什么拓扑排序过不了。直接从 $n$ 出发遍历一下图标记到达过的点就行了.....

## D

看一下除掉 $\gcd$ 后不同的点对有多少就行了。注意 $\gcd$ 要绝对值.....

## E

只能说多年英语白学了。 `exactly` adv. 恰好 。假如你的翻译器没有翻译这个东西，或者你没注意到默认了是至少，那么你会卡死在这个题目。假如整个机房都没有看见，那么就是整个机房都会卡死在这个题目。

假如看见了，那么只有连通块只有呈一个环状即 $n=m$ 时合法，有两种方式。如果出现了一个不是环的连通块直接 `return puts("0"),0` 即可。否则 `ans *= 2ll` 。

## F0

~~直接发现~~ $S(P)$ 就是排列 $P$ 的环长。直接考虑计算答案。

$$
n! \times \prod\limits_{L,F} \frac{1}{(L!)^F \cdot F!} ((L-1)!)^F
$$

DFS 求一下划分即可。

[F0](https://atcoder.jp/contests/abc226/submissions/27114612)

## F1

dp 计数。

把 $i \to p_i$ 连边，得到的图会有很多的环。假如现在有一个 $n$ 个点的图，那么我们根据这个图构造一个排列 $P$ ，但是可能的环的个数只有 $(n-1)!$ 个。

对于一个长度为 $n$ 的错排，把它们移回 `1 2 3 ... n` 这样的排列至少要 $n \cdot d (d >0)$  次。因此，最终答案应该从环中划分出每个可能的最小的大小。即 lcm.

设 $f_{i,j}$ 表示当前的数的划分是 $i$ ，lcm 是 $j$ ，那么每次枚举一个 $x$ 转移：

$$
f_{i,j} \times \binom{n-i-1}{x-1} \times (x-1)! \to f_{i+x, LCM(j, x)}
$$

最终答案：$\sum f_{n,m} \times s^k$

[F1](https://atcoder.jp/contests/abc226/submissions/27150839)

## F2

还是上面那个 dp，但是实际上有用的状态很少，每次都只会从 $j$ 的质因数转移过来，只有 $100$ 左右。所有每次枚举质因数然后乘倍数即可。

顺利最优解

[F2](https://atcoder.jp/contests/abc226/submissions/27152366)

## G

智慧题，懒得丢题解链接了。

最后修改：2021 年 11 月 11 日

如果觉得我的文章对你有用，请随意赞赏

Contest: AtCoder Beginner Contest 226

tony102 • 2021 年 11 月 11 日

Contest: AtCoder Beginner Contest 226

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

丁尼生诗歌节选

20211103 并王 (bing)

多元线性回归的梯度下降算法和标准化操作

写在虎年末

关于一些题解和讲题

Contest: AtCoder Beginner Contest 226

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Contest: AtCoder Beginner Contest 226

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款