一个背包有K种颜色一共N个球，颜色分别为1，2，3…K，颜色相同的球是不区别的。现在从背包里一个一个拿球直到所有球拿光，在拿光第I+1种颜色球之前一定要拿光第I种颜色的球，求有多少种拿法

如果只有一种颜色的球，拿的方法只有一种。如果有两种，留下一个颜色为2的放在最后一个，剩下的N1个颜色1和N2-1个颜色2的可以随意摆，方法数为1*(N1+N2-1 choose N2-1)；如果有三种相当于先排好颜色为1，2的，然后剩下N3-1个颜色为3的插空

代码

继续阅读 →

有T个队伍M道题，给一个T*M的格子Pij表示第第i个队做出第j道题的概率，求每个队至少做出一道题，题数最多队至少做出N道题的概率

手算都算不出来…

这题可以用每个队都做出至少一题的概率P1减去每个队的出题数都在1～N-1的概率P2来算，P1的求法：1-每队都做不出题的概率相乘，dp[i][j][k]表示第i个队在前j道题中解出k道的概率，dp[i][j][k] = dp[i][j-1][k]*(1-p[i][j]) + dp[i][j-1][k-1]*p[i][j]，dp[i][0][0] = 1.0。设s[i][j]表示第i个队做出j道题的概率，s[i][j] = dp[i][M][1] + dp[i][1][2] + … + dp[i][M][j] = (sum_{k=1}^j dp[i][M][k])，那么P2 = (s[1][N-1]-s[1][0])*(s[2][N-1]-s[2][0])*…*(s[T][N-1]-s[T][0]) ，P1 = (s[1][M]-s[1][0])*(s[2][M]-s[2][0])*…*(s[T][M]-s[T][0])

代码

继续阅读 →