首页 > 代码库 > UVa 10288 (期望) Coupons
UVa 10288 (期望) Coupons
题意：
每张彩票上印有一张图案，要集齐n个不同的图案才能获奖。输入n，求要获奖购买彩票张数的期望(假设获得每个图案的概率相同)。
分析：
假设现在已经有k种图案，令s = k/n，得到一个新图案需要t次的概率为：st-1(1-s)；
因此，得到一个新图案的期望为(1-s)(1 + 2s + 3s2 + 4s3 +...)
下面求上式中的级数：
令
则
所以得到一个新图案的期望为：
总的期望为：
这道题的输出很新颖，如果是分数的话，就要以分数形式输出，具体细节详见代码。
1 #include <iostream> 2 #include <sstream> 3 #include <cstdio> 4 using namespace std; 5 typedef long long LL; 6 7 LL gcd(LL a, LL b) 8 { 9 if(b == 0) return a;10 return gcd(b, a % b);11 }12 13 LL lcm(LL a, LL b)14 {15 return a / gcd(a, b) * b;16 }17 18 int LL_length(LL x)19 {20 stringstream ss;21 ss << x;22 return ss.str().length();23 }24 25 void print_chars(char c, int n)26 {27 for(int i = 0; i < n; ++i)28 putchar(c);29 }30 31 void output(LL a, LL b, LL c)32 {33 if(b == 0)34 {35 printf("%lld\n", a);36 return;37 }38 int l = LL_length(a);39 print_chars(‘ ‘, l+1);40 printf("%lld\n", b);41 printf("%lld ", a);42 print_chars(‘-‘, LL_length(c));43 printf("\n");44 print_chars(‘ ‘, l+1);45 printf("%lld\n", c);46 }47 48 int main()49 {50 int n;51 while(scanf("%d", &n) == 1)52 {53 if(n == 1)54 {55 puts("1");56 continue;57 }58 LL x = 1, a = n + 1, b = 0, c;59 for(int i = 2; i <= n-1; ++i)60 x = lcm(x, i);61 c = x;62 x *= n;63 for(int i = 2; i <= n-1; ++i)64 b += x / i;65 a += b / c;66 LL g = gcd(b, c);67 b /= g, c /= g;68 b %= c;69 output(a, b, c);70 }71 72 return 0;73 }
UVa 10288 (期望) Coupons
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。