有无 ABC F 题解法/kel

学术版

zhiyangfan @ 2021-11-07 21:50:12

赛时想到的是所有可能的置换环中每个环大小的 \operatorname{lcm} 的 k 次方之和。

但没想到怎么实现，也不确定正确性。

by Eason_AC @ 2021-11-07 21:52:03

@zhiyangfan 直接枚举这些环长再算一下方案数就可以了，时间复杂度和 50 的拆分数同级，可以过

然而我赛时被卡在了 E 上

by xyf007 @ 2021-11-07 21:52:38

@zhiyangfan 直接 DP，设 f_{i,j} 表示 i 个元素 lcm 为 j 的方案数，然后转移的时候枚举 1 所在环的长度

by zhiyangfan @ 2021-11-07 21:53:06

@Eason_AC /fad/fad 草了，我赛时以为拆分数是 \mathcal{O}(2^n) 的，就没敢写。

还是我理解错了？

by Cocoly1990 @ 2021-11-07 21:53:28

@Eason_AC F是个啥意思啊，看不懂，只看到了尖叫（

by zhiyangfan @ 2021-11-07 21:53:40

@xyf007 草/fad 确实/kk

by Eason_AC @ 2021-11-07 21:54:37

@zhiyangfan 显然不是 \mathcal O(2^n) 吧

反正 n=50 能过（

by zimujun @ 2021-11-07 21:55:04

划分数爆搜

by zhiyangfan @ 2021-11-07 21:55:31

@Eason_AC 好吧（

我写个试试

by xyf007 @ 2021-11-07 21:55:33

@zhiyangfan 拆分数大概能跑 70~80

by zhiyangfan @ 2021-11-07 21:56:12

@xyf007 请问能不能稍微解释一下转移的过程/kel谢谢谢谢

| 下一页