小島みなこの競プロ日常
@algorithm_daily_of_minako
460
subscribers
5.18K
photos
288
videos
283
files
6.95K
links
Download Telegram
Join
小島みなこの競プロ日常
460 subscribers
小島みなこの競プロ日常
这个题还真的挺难的。。。。推清楚的话代码量倒是约等于 0 .。。
小島みなこの競プロ日常
考虑用 GF 处理这个计数问题。。。
小島みなこの競プロ日常
第一步是考虑怎么破环为链。。。但是这里细节有点多。。我们先考虑链的情况吧
小島みなこの競プロ日常
首先可以对 m 进行倍增。。
小島みなこの競プロ日常
想到这一步就成功一大半了。。
小島みなこの競プロ日常
之后我们发现实际上是要计数一个 01 序列。。然后不能出现两个连续的 1.。
小島みなこの競プロ日常
image_2021-10-04_02-10-31.png
3.3 KB
小島みなこの競プロ日常
这个东西一共有五种情况。。。
小島みなこの競プロ日常
核心思想是对这个序列中每次出现两个连续的 0 ,就拆成两个物品,然后去做完全背包。
小島みなこの競プロ日常
搞出 path 之后 cycle 就变得简单了。。。所以核心难点是上面这个 5 种情况。。很容易讨论漏掉。。
小島みなこの競プロ日常
我觉得这个题非常 nice。。。
小島みなこの競プロ日常
https://codeforces.com/blog/entry/95477#comment-845806
Codeforces
Codeforces Round #745 Editorial
I'm very sorry about all the inconvenience, and I would like to bear the blame. Much thanks to those who help me prepare this round. It's not their fault. And much thanks to your participation.
小島みなこの競プロ日常
太神了
小島みなこの競プロ日常
csie.ntu.edu.tw/~bitcoin
and
csie.ntu.edu.tw/~fintech
小島みなこの競プロ日常
https://www.cnblogs.com/dysyn1314/p/13436563.html
Cnblogs
【2020杭电多校round5】HDU6818 Array Repairing - dysyn1314 - 博客园
把序列变成一棵基环树。转化为求所有基环树环的数量之和。可以egf做。设g(n)表示n个节点的基环树森林数量,显然g(n)=n^n。设G(x)是g的egf。则n个节点的一棵基环树的数量就是F=ln G。
小島みなこの競プロ日常
image_2021-10-05_03-55-26.png
112.9 KB
小島みなこの競プロ日常
wait ,这玩意不是可以 O(n) 么
小島みなこの競プロ日常
https://en.wikipedia.org/wiki/Lambert_W_function
Wikipedia
Lambert W function
In mathematics, the Lambert W function, also called the omega function or product logarithm, is a multivalued function, namely the branches of the converse relation of the function f(w) = wew, where w is any complex number and ew is the exponential function.…
小島みなこの競プロ日常
http://oeis.org/A057500
小島みなこの競プロ日常
http://oeis.org/A001429
小島みなこの競プロ日常
http://oeis.org/A001865