SRM 478 Solution。。

哎。这场极度失败的SRM。。。。看来自己不行的地方还有很多啊囧。。。
250:
注意到所有的变换都是x->2^n*x+2^n-1
设F(a,x)=2^n*x+2^n-1,
那么可以证明F(a,F(b,x))=F(a+b,x)..
然后变换只有a=2和a=3.。那么找出最小的t使得F(t,x)%1000…007为0.。。
然后把t表示成2和3的和就OK了。。
悲剧的是我忘了考虑一开始就可以的状态了。。然后果断被Cha。。0分。。
500:
也就是个状态压缩的Dp汗。。
设Ans[subset]为把subset的那些归并成一堆可以得到的钱,
Dp[subset]subset那些可以得到的最大钱
然后穷举一下啊subset的子集就可以了。。
1000:
设sum为所有的取法数,
考虑先算出p[i]=取的时候在第i个盒子里取的概率(就是这个盒子被选中了并且抽中了。。)
根据这个就可以算出全部了。。
设 Dp[total]为选total个苹果的方法总数,Dp2[total]为忽略第i个盒子这样的方法总数,
那么 with=Dp[total]-Dp2[total]就是选第i个盒子这样的方法总数,
那么with/sum*(Size[i]/total)就是这种情况下的概率。。
然后枚举total。。全部+起来就可以搞出p[i]了。。就OK了汗。。
Size[i]是第i个盒子中苹果总数
。。我就是一个傻X。。。

One thought on “SRM 478 Solution。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>