【题意】：有a,b,c三种物品，a和b有无限多件，c只有s件，现在Amjad想拿c这个物品，但是他前面有n个人。现在每人轮流拿一个物品，前n个人是随机拿，而Amjad是有目的性去拿，问Amjad取得c的概率是多少。
 
【题解】：概率dp。
               设dp[i][j]表示前 i 个人取完还有 j 个 C的概率。
               转移 ：dp[i][j] = dp[i-1][j] * 2 / 3 + dp[i-1][j+1] / 3;
               最后ans = ( ∑dp[n][i], 1 <= i <= s ) / ( ∑dp[n][i], 0 <= i <= s)。
               实现时使用了滚动数组。
 
【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 double dp[60];
19 int n, s;
20 double sum;
21 int main() {
22     while(~scanf("%d%d", &n, &s)) {
23         memset(dp, 0, sizeof(dp));
24         dp[s] = 1.0, sum = 0.0;
25         for(int i = 1; i <= n; i++) 
26             for(int j = 0; j <= s; j++)
27                 dp[j] = dp[j] * 2 / 3 + dp[j+1] / 3;
28         for(int i = 0; i <= s; i++) sum += dp[i];
29         double ans = 100.0 * (sum - dp[0]) / sum;
30         printf("%.5f\n", ans);
31     }
32     return 0;
33 }
34