帖子发自 每一天快乐
-
-
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
不过其实我主要一直是觉得分解质因数这步可能没什么好的办法。。
-
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
-
-
-
-
-
1 小时前, Kris Dreemurr 说道:
那么用讨论的方式发怎么样
感觉还是不大合适,因为我认为关于番剧or系列作品的讨论一般都在某番刚放映时就已经在一手放映地址处被讨论得差不多了,到后面的讨论基本只会由那些该作品在其心中具有特殊意义的死忠粉来进行,而不应该是我这种只是单纯觉得好看,却说不出到底好在哪,只能看dalao讲解的观众来完成。。而这时候反而讨论容易演化成跟其他作品的对比或对剧中矛盾的争论,也不是我想看到的局面。。
如果想推荐这部番的话,我认为发起更粗略一点的话题,如“你们觉得这季度有哪些番好看”,“哪些番值得一看”会更好,但我不太喜欢发起这样具有引导性质的话题。。而喜欢讨论一些更具体一点的东西,或者说可能更愿意在这样的贴子底下留下一些自己的简略评论
所以。。如果dalao有想接触一些优秀番剧之类的想法的话,我感觉您倒是可以发起一个我上面提到的类似主题的讨论贴
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
来这里给各位新手一股清流,高中党来玩玩
在 新手保护区
发布于 · ,由每一天快乐修改
emmm行吧,用一种方法最好弄懂什么情况下能用,为什么能生效,而不是机械地记住一些方法名词
至于下面那个求和
待定系数法:∑n^2=f(n)=an^3+bn^2+cn+d,n取几个值来解出abcd即得通项
另外一类方法的其中一种,累次求和升幂
∑∑k=∑k(k+1)/2=∑k(n-k)
∑k(3k+1)/2=n∑k
(3/2)∑k^2=
(n(n+1)/2)(n+1/2)
∑k^2=(1/6)*n(n+1)(2n+1)
可以想想为什么能这样解。。