cirno. ⑨ Adjacent Numbers

cirno. ⑨ Adjacent Numbers

ZOJ3374. ⑨连号!

downloadsource code (ZOJ3374.cpp) [动态规划(DP), 计数(counting)]

此题捏的是在今年六月,也就是新手上路选拔最后一场前,闹得沸沸扬扬的浙江青田经适房摇号出现五连号的新闻。该新闻引发了全民研究概率论的热潮,在cc98和freecity ZOL也都有很多人参与研究讨论,而有关报道中所算出的概率更是印证了妓者+砖家=智商无下限,有关新闻报道网上好多,不了解的可以考古看看。于是我就出了这么一道加强版的题目,当然笨蛋⑨琪露诺小朋友可是活泼纯情的姑娘,她和专家们可是截然不同的。

  • 湖上の氷精/氷の小さな妖精/チルノ
  • 冬の忘れ物/レティ・ホワイトロック

幻想乡的少女们做成一圈,为选出下一作东方弹幕格斗游戏自机进行摇号,786个号里摇出了203个号,结果坐在一起的灵梦、紫、魔理沙、爱丽丝、咲夜、蕾米莉亚、妖梦、幽幽子和早苗(本次月赛我が東風谷早苗ちゃん只打了个酱油>_<)9位同时入选。落选的黑幕蕾迪·霍瓦特罗克对公正性表示怀疑,而琪露诺也表示这种事情发生的概率只有”0.000,あたい,最強,…%”。现在希望你能帮助求出从围成圈的n个人中,选出m个人,其中包含⑨连号的概率,十连号也是一种九连号。

首先我们来考虑,从站成一列的n个人里选m个人,不出现l连号的方案数。这个我不会网上好多神奇的,结果各异的组合数学公式算法,我只会老老实实的复杂度为O(nml)的动态规划,记dp[i][j][k]表示在前i个人里选了j个人,且最后连续k个人都被选中的方案数,那么显然有:

  • dp[i][0][0] = 1;
  • dp[i][j][0] = sum{dp[i - 1][j][k] | k < l};
  • dp[i][j][k] = dp[i - 1][j - 1][k - 1].

注意到实质上dp[i][j][k] = dp[i - k][j - k][0],所以只要一个二维空间的数组就可以了。这样可以得到,取l=5,dp[786+1][203][0] = 1.651418e+193,总的可能有{786 \choose 203} = 3.217383e+193,于是可以求出五连号的概率大约是48.672%……弱弱地粗略的估计一下,这大概好像可能就是一半吧……

有了上面的基础,我们再来求围成一个圈的n个人里选m个人,不出现9连号的方案数。方法很简单,我们确定一个位置,把这个环剪开,成链,我们只要保证链上没有9连号,剪开的地方也不是9连号就好了。于是我们枚举剪开的地方到底是几连号,设两头分别是i连号和j连号,那么不出现9连号的方案数就是sum{dp[n - (i + 1) - (j + 1) + 1][m - i - j][0] | i + j < 9}。有了方案数,概率可得。

附件:截图来源IOSYS的「チルノのパーフェクトさんすう教室」《琪露诺的完美算术教室》(flash/swf)

[http://watashi.ws/file/cirnos-perfect-math-class.swf](object not displayed)

想来⑨舞也是红遍大江南北呢,当时在acfun上可以看到天朝各地的⑨舞。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

3 Responses to “cirno. ⑨ Adjacent Numbers”
  1. lccycc says:

    太邪恶了 居然不用高精度~

  2. vout says:

    还是想不明白,不应该是dp[i][j][k] = dp[i - 1][j - 1][k - 1]吗?

  3.  
Leave a Reply