链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=35396
【思路】
DP+概率
见白书。
【代码】
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 5 const int N = 100+10; 6 7 int n,a,b; 8 double f[N][N]; 9 10 int main() { 11 int T,kase=0; 12 scanf("%d",&T); 13 while(T--) { 14 scanf("%d/%d%d",&a,&b,&n); 15 double p=(double)a/b; 16 memset(f,0,sizeof(f)); 17 f[0][0]=1; 18 for(int i=1;i<=n;i++) 19 for(int j=0;j*b<=a*i;j++) { 20 f[i][j]=f[i-1][j]*(1-p); 21 if(j) f[i][j] += f[i-1][j-1]*p; 22 } 23 double Q=0; 24 for(int j=0;j*b<=a*n;j++) Q += f[n][j]; 25 printf("Case #%d: %d\n",++kase,(int)(1/Q)); 26 } 27 return 0; 28 }