题目链接题意：　　给一个质地均匀的n的骰子，求投掷出所有点数至少一次的期望次数。 思路：　　这就是一个经典的邮票收集问题（CouponCollectorProblem）。　　投掷出第一个未出现的点数的概率为n/n=1，因为第一次投掷必然是未出现的。　　第二个未出现的点数第一次出现的概率为(n-1)/n，因为有...

题目链接题意：　　地上有n种棍子，其中有两种类型，一种类型是可识别，一种类型是不可识别，每个棍子都有一个权值。　　当你捡到可识别的，那么你以后就不会再捡这个棍子，如果是不可识别的，那么你有可能还会捡。　　问将所有棍子收集完的权值的期望。 思路：　　此题借鉴参考了此篇文章：AladdinandtheMagica...

题目链接 题意：　　在一个1XN的格子上，每个格子都有一定的黄金，你从第一个格子出发，问到最后一个格子得到黄金的期望。　　每次前进使用骰子投点来决定前进步数，如果投出的点前进后会超过N，那么就重新投掷。 思路：　　很直接的期望题。　　概率dp求期望是从后往前求，每次的概率为1/6.　　dp[i]=1...

题目链接题意：　　你在一个迷宫里，开始的时候你面前有n个门，选择每个门的概率相等，有两种结果：　　1）回到|x|分钟之前(x为负时)　　2）x分钟之后出迷宫(x为正时)　　每次回到|x|分钟之前，你都记不得你曾经选过哪扇门　　问走出迷宫所用时间的期望。 思路：　　因为每次都不记得曾经的选择，所以每次的期望都是...

题目链接题意：　　　　给一个文档，这个文档由yes、no组成，共有s个byte，共有n个yes、no。　　　　假设yes的个数为yes_num,no的个数为no_num。　　　　将这n个数进行排列，对于每个排列，将其右移一个结果，并在最左端补上yes，再将其与原排列进行对比，看有多少个不同的。　　　　计算所有排列中不同...