题意:
每张彩票上印有一张图案,要集齐n个不同的图案才能获奖。输入n,求要获奖购买彩票张数的期望(假设获得每个图案的概率相同)。
分析:
假设现在已经有k种图案,令s = k/n,得到一个新图案需要t次的概率为:st-1(1-s);
因此,得到一个新图案的期望为(1-s)(1 + 2s + 3s2 + 4s3 +…)
下面求上式中的级数:
这道题的输出很新颖,如果是分数的话,就要以分数形式输出,具体细节详见代码。
#include <iostream>
#include <sstream>
#include <cstdio>
using namespace std;
typedef long long LL; LL gcd(LL a, LL b)
{
if(b == ) return a;
return gcd(b, a % b);
} LL lcm(LL a, LL b)
{
return a / gcd(a, b) * b;
} int LL_length(LL x)
{
stringstream ss;
ss << x;
return ss.str().length();
} void print_chars(char c, int n)
{
for(int i = ; i < n; ++i)
putchar(c);
} void output(LL a, LL b, LL c)
{
if(b == )
{
printf("%lld\n", a);
return;
}
int l = LL_length(a);
print_chars(' ', l+);
printf("%lld\n", b);
printf("%lld ", a);
print_chars('-', LL_length(c));
printf("\n");
print_chars(' ', l+);
printf("%lld\n", c);
} int main()
{
int n;
while(scanf("%d", &n) == )
{
if(n == )
{
puts("");
continue;
}
LL x = , a = n + , b = , c;
for(int i = ; i <= n-; ++i)
x = lcm(x, i);
c = x;
x *= n;
for(int i = ; i <= n-; ++i)
b += x / i;
a += b / c;
LL g = gcd(b, c);
b /= g, c /= g;
b %= c;
output(a, b, c);
} return ;
}
代码君