转跳到内容

偶得的一道数学/算法相关题


只显示该作者

只有该作者的内容显示中。 返回到主题

推荐贴

gaitubao_Fgw92Ad_SwZLAoDOYblsdHEUDb-o_gaitubao_.jpg.5669fc69a22c90fce78191e976a3a72e.jpg因为觉得很有趣所以就发个帖题目挑战一试了,上附题图(但也没找到图来源)

关于解答:我由于对算法竞赛标准没什么了解,如有要求作答的话,基本只会从数学角度给出一个解答,对题图所要求的输入输出限制就恕无能为力啦_(:з」∠)_

,由每一天快乐修改
细节修改
注释
Eternalcycle Eternalcycle 50.00节操
链接到点评
9 分钟前, Whiteying 说道:

数论算法不会,只会搜索的菜鸡,图来源是八月社经典galgame《秽翼的尤斯蒂亚》中艾莉丝·弗罗拉莉的CG:b2:

gal来源我倒是清楚的, 只是有关这题出自谁之手,从哪流传出来的讯息就一无所知了(因为也一定程度上算转载嘛)_(:з」∠)_

链接到点评
28 分钟前, Whiteying 说道:

这样啊,虽然我也不知道出自哪,但题目大概率是出自HDU、洛谷、牛客这几个网站。

已经从学校的ACM-ICPC社团毕业了,大约有一两年没接触算法,全部成了青春的回忆了:YangTuo_Y:

是dalao。。想必这种在社团跟队友一起努力学习的回忆一定非常美好

链接到点评
5 分钟前, jas 说道:

随便想了下,大概可以把g表示成质数的乘积,列举可能的下一个g,用全期望公式计算
因为g只会变小,S中整数数量n只会变多,所以从g=1、n最大的状态倒推,就能一次一个地得出结果了

时间复杂度大概是o(n^2)~o(n^3)?

感觉思路应该是可行的,但是每步推行策略的具体操作能否再详细一点呢。。而且我也很好奇复杂度是如何快速估计出来的(我没有这种直觉)

链接到点评
30 分钟前, jas 说道:

随便想了下,大概可以把g表示成质数的乘积,列举可能的下一个g,用全期望公式计算
因为g只会变小,S中整数数量n只会变多,所以从g=1、n最大的状态倒推,就能一次一个地得出结果了

时间复杂度大概是o(n^2)~o(n^3)?

毕竟这种题关键应该就在于分类及复杂度大小吧,如何进行分类及分类的具体实现,后续都是重复操作

链接到点评
22 小时前, jas 说道:

 

设S(g,n)代表gcd=g,已添加原料个数=n的状态。E(g,n)代表继续添加原料个数的期望。那么原题就是求E(g,0)。

对g分解因数,得到g的质因数列表a[t],对应指数列表b[t],有
g = a0^b0 + a1^b1 + ... + at^bt,

于是,后继的g能表示为
g' = a0^c0 + a1^c1 + ... + at^ct,其中ci满足0<=ci<=bi

接下来要遍历[c0,c1,...ct]的组合,算出每种组合的概率P((g',n+1)|(g,n))和期望E(g',n+1),相乘再累加,就得到了要求的E(g,n)

    概率P((g',n+1)|(g,n))的计算:
        1.如果bi>ci,则将对应的ai记入集合d
        2.从1~int(m/g')的整数中,筛掉集合d的成员的倍数。剩余数字的个数cnt,即为S(g,n)->S(g',n+1)的途径数
        3.S(g,n)时,有m-n个数可选。因此概率为cnt/(m-n)

    期望E(g',n+1)的计算:
        递归。显然递归次数小于m,能在有限步内完成。可以开个hashmap做缓存

    递归的边界条件:
        1. g=1时,不用继续。E(1,x) = 0
        2. n>=m/g时,g的倍数全部加进S了,下个g一定变小。P((g,n+1)|(g,n)) = 0

例如,m=100时,求E(60,1)
    1. 60 = 2^2 * 3^1 * 5^1, 得 a=[2,3,5], b=[2,1,1],需遍历(2+1)*(1+1)*(1+1)=12种状态
    2. 以c=[1,0,1]为例,这时g‘= 2^1 * 5^1 = 10,对应S(10,2)
        a) b0>c0, b1>c1, b2=c2, 得到的集合d为{a0,a1} = {2,3}
        b) 从不超过100/10=10的整数中,去掉2和3的倍数,剩余3个数(即1,5,7)。所以有3个数能使g变成10(即10,50,70)
        c) result += 3 * E(10,2),这一步要递归计算E(10,2)
    3. c的遍历结束后,result/(100-1),就是E(60,1)

 

那个复杂度估得很松:因为E(g,0)有两个维度,可能要计算g*m个状态。如果g m成比例,就成了m^2。再假设每个子状态需要k~mk次运算,相乘就是m^2~m^3

辛苦了_(:з」∠)_,写得如此详细,tql

链接到点评
22 小时前, jas 说道:

 

设S(g,n)代表gcd=g,已添加原料个数=n的状态。E(g,n)代表继续添加原料个数的期望。那么原题就是求E(g,0)。

对g分解因数,得到g的质因数列表a[t],对应指数列表b[t],有
g = a0^b0 + a1^b1 + ... + at^bt,

于是,后继的g能表示为
g' = a0^c0 + a1^c1 + ... + at^ct,其中ci满足0<=ci<=bi

接下来要遍历[c0,c1,...ct]的组合,算出每种组合的概率P((g',n+1)|(g,n))和期望E(g',n+1),相乘再累加,就得到了要求的E(g,n)

    概率P((g',n+1)|(g,n))的计算:
        1.如果bi>ci,则将对应的ai记入集合d
        2.从1~int(m/g')的整数中,筛掉集合d的成员的倍数。剩余数字的个数cnt,即为S(g,n)->S(g',n+1)的途径数
        3.S(g,n)时,有m-n个数可选。因此概率为cnt/(m-n)

    期望E(g',n+1)的计算:
        递归。显然递归次数小于m,能在有限步内完成。可以开个hashmap做缓存

    递归的边界条件:
        1. g=1时,不用继续。E(1,x) = 0
        2. n>=m/g时,g的倍数全部加进S了,下个g一定变小。P((g,n+1)|(g,n)) = 0

例如,m=100时,求E(60,1)
    1. 60 = 2^2 * 3^1 * 5^1, 得 a=[2,3,5], b=[2,1,1],需遍历(2+1)*(1+1)*(1+1)=12种状态
    2. 以c=[1,0,1]为例,这时g‘= 2^1 * 5^1 = 10,对应S(10,2)
        a) b0>c0, b1>c1, b2=c2, 得到的集合d为{a0,a1} = {2,3}
        b) 从不超过100/10=10的整数中,去掉2和3的倍数,剩余3个数(即1,5,7)。所以有3个数能使g变成10(即10,50,70)
        c) result += 3 * E(10,2),这一步要递归计算E(10,2)
    3. c的遍历结束后,result/(100-1),就是E(60,1)

 

那个复杂度估得很松:因为E(g,0)有两个维度,可能要计算g*m个状态。如果g m成比例,就成了m^2。再假设每个子状态需要k~mk次运算,相乘就是m^2~m^3

不过其实我主要一直是觉得分解质因数这步可能没什么好的办法。。

每一天快乐遭妹子发现人渣诚本质并被柴刀,求医花去了-2节操

链接到点评
  • 骚男锁定了本主题
游客
此主题已关闭。
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款