题目大意
有r*s张扑克牌，数字从1到 r，每种数字有s种颜色。
询问对于所有随机的d张牌，能选出c张组成顺子的概率和组成同花的概率。
解题分析
对于组成顺子的概率，令dp[i][j][k]表示一共选出了i张牌，数字从1~j，最后有k张牌是顺子。对于每个数字进行考虑，有0~s种选法。要保证连续c张牌的顺子。
对于组成同花的概率，令dp[i][j]表示一共选出了i张牌，颜色从1~j，。对于每种颜色进行考虑，有0~r种选法。要保证没有c张牌是相同颜色的。
最后用高精度来输出答案。
参考程序
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N=30; 5 6 class bign 7 { 8 public: 9 enum {MAXN = 100}; 10 int len, s[MAXN]; 11 void clean() 12 { 13 while(len > 1 && !s[len-1]) len--; 14 } 15 bign () 16 { 17 memset(s, 0, sizeof(s)); 18 len = 1; 19 } 20 bign (int num) { *this = num; } 21 bign (long long num) { *this = num; } 22 bign (const char *num) { *this = num; } 23 bign operator = (const long long num) 24 { 25 char s[MAXN]; 26 sprintf(s, "%I64d", num); 27 *this = s; 28 return *this; 29 } 30 bign operator = (const int num) 31 { 32 char s[MAXN]; 33 sprintf(s, "%d", num); 34 *this = s; 35 return *this; 36 } 37 bign operator = (const char *num) 38 { 39 for(int i = 0; num[i] == '0' && num[1]!=' '; num++) ; //去前导0 40 len = strlen(num); 41 for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; 42 return *this; 43 } 44 bign operator + (const bign &b) const //+ 45 { 46 bign c; 47 c.len = 0; 48 for(int i = 0, g = 0; g || i < max(len, b.len); i++) 49 { 50 int x = g; 51 if(i < len) x += s[i]; 52 if(i < b.len) x += b.s[i]; 53 c.s[c.len++] = x % 10; 54 g = x / 10; 55 } 56 return c; 57 } 58 bign operator += (const bign &b) 59 { 60 *this = *this + b; 61 return *this; 62 } 63 bign operator * (const int x) 64 { 65 bign c; 66 int j=0; for (int y=x;y;y/=10,j++); 67 c.len = len + j; 68 for(int i = 0; i < len; i++) 69 c.s[i] = s[i] * x; 70 71 for(int i = 0; i < c.len; i++) 72 { 73 c.s[i+1] += c.s[i]/10; 74 c.s[i] %= 10; 75 } 76 c.clean(); 77 return c; 78 } 79 bign operator * (const bign &b) //* 80 { 81 bign c; 82 c.len = len + b.len; 83 for(int i = 0; i < len; i++) 84 { 85 for(int j = 0; j < b.len; j++) 86 { 87 c.s[i+j] += s[i] * b.s[j]; 88 } 89 } 90 for(int i = 0; i < c.len; i++) 91 { 92 c.s[i+1] += c.s[i]/10; 93 c.s[i] %= 10; 94 } 95 c.clean(); 96 return c; 97 } 98 bign operator *= (const bign &b) 99 { 100 *this = *this * b; 101 return *this; 102 } 103 bign operator *= (const int x) 104 { 105 *this = *this * x; 106 return *this; 107 } 108 bign operator - (const bign &b) 109 { 110 bign c; 111 c.len = 0; 112 for(int i = 0, g = 0; i < len; i++) 113 { 114 int x = s[i] - g; 115 if(i < b.len) x -= b.s[i]; 116 if(x >= 0) g = 0; 117 else 118 { 119 g = 1; 120 x += 10; 121 } 122 c.s[c.len++] = x; 123 } 124 c.clean(); 125 return c; 126 } 127 bign operator -= (const bign &b) 128 { 129 *this = *this - b; 130 return *this; 131 } 132 bign operator / (const bign &b) 133 { 134 bign c, f = 0; 135 for(int i = len-1; i >= 0; i--) 136 { 137 f = f*10; 138 f.s[0] = s[i]; 139 while(f >= b) 140 { 141 f -= b; 142 c.s[i]++; 143 } 144 } 145 c.len = len; 146 c.clean(); 147 return c; 148 } 149 bign operator /= (const bign &b) 150 { 151 *this = *this / b; 152 return *this; 153 } 154 bign operator % (const bign &b) 155 { 156 bign r = *this / b; 157 r = *this - r*b; 158 return r; 159 } 160 bign operator %= (const bign &b) 161 { 162 *this = *this % b; 163 return *this; 164 } 165 bool operator < (const bign &b) 166 { 167 if(len != b.len) return len < b.len; 168 for(int i = len-1; i >= 0; i--) 169 { 170 if(s[i] != b.s[i]) return s[i] < b.s[i]; 171 } 172 return false; 173 } 174 bool operator > (const bign &b) 175 { 176 if(len != b.len) return len > b.len; 177 for(int i = len-1; i >= 0; i--) 178 { 179 if(s[i] != b.s[i]) return s[i] > b.s[i]; 180 } 181 return false; 182 } 183 bool operator == (const bign &b) 184 { 185 return !(*this > b) && !(*this < b); 186 } 187 bool operator != (const bign &b) 188 { 189 return !(*this == b); 190 } 191 bool operator <= (const bign &b) 192 { 193 return *this < b || *this == b; 194 } 195 bool operator >= (const bign &b) 196 { 197 return *this > b || *this == b; 198 } 199 operator string() const 200 { 201 string res = ""; 202 for(int i = 0; i < len; i++) res = char(s[i]+'0') + res; 203 return res; 204 } 205 friend istream& operator >> (istream &in, bign &x) 206 { 207 string s; 208 in >> s; 209 x = s.c_str(); 210 return in; 211 } 212 friend ostream& operator << (ostream &out, const bign &x) 213 { 214 out << string(x); 215 return out; 216 } 217 }; 218 219 int r,s,d,c; 220 int C[N][N]; 221 bign dp[N][N]; 222 bign f[N][N][N]; 223 224 bign calc_1(int n,int k) 225 { 226 bign tmp=1; 227 for (int i=1;i<=k;i++) 228 { 229 tmp=tmp*(n-(i-1)); 230 tmp=tmp/i; 231 } 232 return tmp; 233 } 234 235 bign gcd(bign x,bign y) 236 { 237 //return y>0?gcd(y,x % y):x; 238 bign tmp; 239 if (y>0) tmp=gcd(y,x % y); else tmp=x; 240 return tmp; 241 } 242 243 int main() 244 { 245 freopen("poker.in","r",stdin); 246 freopen("poker.out","w",stdout); 247 248 for (int i=0;i<N;i++) C[i][0]=1; 249 for (int i=1;i<N;i++) 250 for (int j=1;j<=i;j++) 251 C[i][j]=C[i-1][j]+C[i-1][j-1]; 252 253 cin.sync_with_stdio(0); 254 while (cin>>r>>s>>d>>c) 255 { 256 if (!r && !s && !d && !c) break; 257 258 memset(f,0,sizeof(f)); 259 for (int j=0;j<=r;j++) f[0][j][0]=1; 260 for (int i=1;i<=d;i++) 261 for (int j=1;j<=r;j++) 262 { 263 for (int k=0;k<=min(i,c-1);k++) 264 f[i][j][0]+=f[i][j-1][k]; 265 for (int k=1;k<=min(j,c-1);k++) 266 for (int l=1;l<=min(i,s);l++) 267 f[i][j][k]+=f[i-l][j-1][k-1]*C[s][l]; 268 } 269 bign ans=0; 270 for (int k=0;k<=c-1;k++) ans+=f[d][r][k]; 271 bign a=calc_1(r*s,d),b=a-ans; 272 cout<<b/gcd(a,b)<<"/"<<a/gcd(a,b)<<endl; 273 274 memset(dp,0,sizeof(dp)); 275 for (int j=0;j<=s;j++) dp[0][j]=1; 276 for (int i=1;i<=d;i++) 277 for (int j=1;j<=s;j++) 278 for (int k=0;k<=min(i,c-1);k++) 279 dp[i][j]+=dp[i-k][j-1]*C[r][k]; 280 a=calc_1(r*s,d),b=a-dp[d][s]; 281 cout<<b/gcd(a,b)<<"/"<<a/gcd(a,b)<<endl<<endl; 282 } 283 }