uoj #450[集训队作业2018]复读机

忘是亡心i 2021-12-13 04:38 221阅读 0赞

[传送门][Link 1]

\\(d=1\\),那么任何时刻都可以\\(k\\)个复读机的一种,答案为\\(k^n\\)

\\(d>1\\),可以枚举某个复读机的复读次数(必须是\\(d\\)的倍数),然后第\\(i\\)个复读时间为\\(x\_i\\),那么答案为\\(n!\\sum\\limits\_\{d|x\_i,\\sum x\_i=n\} \\prod \\frac\{1\}\{x\_i!\}\\),这个显然可以暴力背包生成函数,因为有\\(d|x\_i\\)的限制,那么可以套用单位根反演,单个复读机的生成函数为\\(\\sum\_\{i=0\}^\{\\infty\}\[d|i\]\\frac\{x^i\}\{i!\}\\),也就是

\\\[\\frac\{1\}\{d\}\\sum\_\{i=0\}^\{\\infty\}\\sum\_\{j=0\}^\{d-1\}\\omega\_\{d\}^\{ij\}\\frac\{x^i\}\{i!\}\\\]\\\[\\frac\{1\}\{d\}\\sum\_\{j=0\}^\{d-1\}\\sum\_\{i=0\}^\{\\infty\}\\frac\{\\omega\_\{d\}^\{ij\}x^i\}\{i!\}\\\]\\\[\\frac\{1\}\{d\}\\sum\_\{i=0\}^\{d-1\}e^\{\\omega\_\{d\}^\{i\}x\}\\\]

然后求出这个生成函数的\\(k\\)次方的\\(n\\)次项系数乘上\\(n!\\)就好了(注意到\\(n!\\)会和\\(n\\)次项中的\\(\\frac\{1\}\{n!\}\\)抵消),实现的时候把\\(e^x\\)看成未知数,枚举\\(e^\{\\omega\_\{d\}^\{0\}x\},e^\{\\omega\_\{d\}^\{1\}x\},(d=3\\)时有\\(e^\{\\omega\_\{d\}^\{2\}x\})\\)出现了多少次,然后系数乘上组合数即可(说白了就是二项式定理展开)

[代码][Link 2]

转载于:https://www.cnblogs.com/smyjr/p/10907471.html

[Link 1]: http://uoj.ac/problem/450
[Link 2]: http://uoj.ac/submission/347601

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关 1108 String复读机（JAVA）

给定一个长度不超过 104 的、仅由英文字母构成的字符串。请将字符重新调整顺序，按 `StringString....` （注意区分大小写）这样的顺序输出，并忽略其它字符。当然

Myth丶恋晨/ 2023年09月28日 20:05/ 0 赞/ 22 阅读

相关磁带转换成MP3 文件，摆脱复读机

一、就是3.5接口的直录线，2元一根，接入声卡的Line IN口，另一端接入录音机的耳机口，用goldwave或Audition.exe录音，在音量属性中选录音选

曾经终败给现在/ 2022年06月18日 01:56/ 0 赞/ 202 阅读

相关集训队分组

中南大学ACM的暑期集训马上就要开始了，这次集训会将全体N名集训队员（编号分别为1, 2, …, N）按集训选拔赛的排名分成两组，前K名队员分入A组，其余队员分入B组

Dear 丶/ 2022年06月14日 07:52/ 0 赞/ 236 阅读

相关牛客训练（处女座与复读机）dp解法

大佬的思想：[https://blog.csdn.net/snayf/article/details/86632559][https_blog.csdn.net_snayf_a

曾经终败给现在/ 2022年04月23日 07:12/ 0 赞/ 222 阅读

相关 6. 寻找复读机

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

叁歲伎倆/ 2022年04月04日 07:18/ 0 赞/ 190 阅读

相关 UOJ#449. 【集训队作业2018】喂鸽子

[\449. 【集训队作业2018】喂鸽子][449. _2018] DP好题法一：min-max容斥处理前m个，最快吃饱的鸽子期望的时间根据期望的定义

本是古典何须时尚/ 2021年12月23日 15:25/ 0 赞/ 242 阅读

相关 uoj#402. 【CTSC2018】混合果汁（主席树+二分）

[传送门][Link 1] 我们先把果汁按照美味度排序，枚举\\(d\\)，那么肯定是贪心的选择美味程度不小于\\(d\\)的且最便宜的果汁发现\\(d\\)可以二分，那

待我称王封你为后i/ 2021年12月23日 05:37/ 0 赞/ 242 阅读

相关处女座与复读机

链接：[https://ac.nowcoder.com/acm/contest/327/G][https_ac.nowcoder.com_acm_contest_327_G]

刺骨的言语ヽ痛彻心扉/ 2021年12月15日 08:47/ 0 赞/ 266 阅读

相关 uoj #450[集训队作业2018]复读机

[传送门][Link 1] \\(d=1\\),那么任何时刻都可以\\(k\\)个复读机的一种,答案为\\(k^n\\) \\(d>1\\),可以枚举某个复读机的复读次数(

忘是亡心i/ 2021年12月13日 04:38/ 0 赞/ 222 阅读

相关 UOJ399 CTSC2018 假面期望、DP

[传送门][Link 1] -------------------- \\(Q \\leq 200000 , C \\leq 1000 , m\_i \\leq 100\\

水深无声/ 2021年11月09日 02:02/ 0 赞/ 258 阅读