Yinyangshi is a famous RPG game on mobile phones.
Kim enjoys collecting cards in this game. Suppose there are n kinds of cards. If you want to get a new card, you need to pay W coins to draw a card. Each time you can only draw one card, all the cards appear randomly with same probability 1/n. Kim can get 1 coin each day. Suppose Kim has 0 coin and no cards on day 0. Every W days, Kim can draw a card with W coins. In this problem ,we define W=(n-1)!.
Now Kim wants to know the expected days he can collect all the n kinds of cards.
Input
The first line an integer T(1 ≤ T ≤ 10). There are T test cases.
The next T lines, each line an integer n. (1≤n≤3000)
Output
For each n, output the expected days to collect all the n kinds of cards, rounded to one decimal place.
Sample Input
4
1
2
5
9
Sample Outpu1.0
3.0
274.0
1026576.0 队友推出公式为
ans = n * ( 1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n );
看到n比较大 然后我就直接上大数了
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define pi acos(-1.0)
#define eps 1e-6
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define bug printf("******\n")
#define mem(a,b) memset(a,b,sizeof(a))
#define fuck(x) cout<<"["<<x<<"]"<<endl
#define f(a) a*a
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define pf printf
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define FIN freopen("DATA.txt","r",stdin)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) x&-x
#pragma comment (linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
const int INF = 0x7fffffff;
const int mod = 1e9 + ;
const int maxn = 1e5 + ;
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4
class BigNum {
private:
int a[(int)1e4 + ]; //可以控制大数的位数
int len; //大数长度
public:
BigNum() {
len = ;
memset(a, , sizeof(a));
} //构造函数
BigNum(const int); //将一个int类型的变量转化为大数
BigNum(const char *); //将一个字符串类型的变量转化为大数
BigNum(const BigNum &); //拷贝构造函数
BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算 friend istream &operator>>(istream &, BigNum &); //重载输入运算符
friend ostream &operator<<(ostream &, BigNum &); //重载输出运算符 BigNum operator+(const BigNum &) const; //重载加法运算符，两个大数之间的相加运算
BigNum operator-(const BigNum &) const; //重载减法运算符，两个大数之间的相减运算
BigNum operator*(const BigNum &) const; //重载乘法运算符，两个大数之间的相乘运算
BigNum operator/(const int &) const; //重载除法运算符，大数对一个整数进行相除运算 BigNum operator^(const int &) const; //大数的n次方运算
int operator%(const int &) const; //大数对一个int类型的变量进行取模运算
bool operator>(const BigNum &T) const; //大数和另一个大数的大小比较
bool operator>(const int &t) const; //大数和一个int类型的变量的大小比较 void print(); //输出大数
}; BigNum::BigNum(const int b) { //将一个int类型的变量转化为大数
int c, d = b;
len = ;
memset(a, , sizeof(a));
while (d > MAXN) {
c = d - (d / (MAXN + )) * (MAXN + );
d = d / (MAXN + );
a[len++] = c;
}
a[len++] = d;
} BigNum::BigNum(const char *s) { //将一个字符串类型的变量转化为大数
int t, k, index, l, i;
memset(a, , sizeof(a));
l = strlen(s);
len = l / DLEN;
if (l % DLEN)
len++;
index = ;
for (i = l - ; i >= ; i -= DLEN) {
t = ;
k = i - DLEN + ;
if (k < )
k = ;
for (int j = k; j <= i; j++)
t = t * + s[j] - '';
a[index++] = t;
}
} BigNum::BigNum(const BigNum &T) : len(T.len) { //拷贝构造函数
int i;
memset(a, , sizeof(a));
for (i = ; i < len; i++)
a[i] = T.a[i];
} BigNum &BigNum::operator=(const BigNum &n) { //重载赋值运算符，大数之间进行赋值运算
int i;
len = n.len;
memset(a, , sizeof(a));
for (i = ; i < len; i++)
a[i] = n.a[i];
return *this;
} istream &operator>>(istream &in, BigNum &b) { //重载输入运算符
char ch[MAXSIZE * ];
int i = -;
in >> ch;
int l = strlen(ch);
int count = , sum = ;
for (i = l - ; i >= ;) {
sum = ;
int t = ;
for (int j = ; j < && i >= ; j++, i--, t *= ) {
sum += (ch[i] - '') * t;
}
b.a[count] = sum;
count++;
}
b.len = count++;
return in; } ostream &operator<<(ostream &out, BigNum &b) { //重载输出运算符
int i;
cout << b.a[b.len - ];
for (i = b.len - ; i >= ; i--) {
cout.width(DLEN);
cout.fill('');
cout << b.a[i];
}
return out;
} BigNum BigNum::operator+(const BigNum &T) const { //两个大数之间的相加运算
BigNum t(*this);
int i, big; //位数
big = T.len > len ? T.len : len;
for (i = ; i < big; i++) {
t.a[i] += T.a[i];
if (t.a[i] > MAXN) {
t.a[i + ]++;
t.a[i] -= MAXN + ;
}
}
if (t.a[big] != )
t.len = big + ;
else
t.len = big;
return t;
} BigNum BigNum::operator-(const BigNum &T) const { //两个大数之间的相减运算
int i, j, big;
bool flag;
BigNum t1, t2;
if (*this > T) {
t1 = *this;
t2 = T;
flag = ;
} else {
t1 = T;
t2 = *this;
flag = ;
}
big = t1.len;
for (i = ; i < big; i++) {
if (t1.a[i] < t2.a[i]) {
j = i + ;
while (t1.a[j] == )
j++;
t1.a[j--]--;
while (j > i)
t1.a[j--] += MAXN;
t1.a[i] += MAXN + - t2.a[i];
} else
t1.a[i] -= t2.a[i];
}
t1.len = big;
while (t1.a[t1.len - ] == && t1.len > ) {
t1.len--;
big--;
}
if (flag)
t1.a[big - ] = - t1.a[big - ];
return t1;
} BigNum BigNum::operator*(const BigNum &T) const { //两个大数之间的相乘运算
BigNum ret;
int i, j, up;
int temp, temp1;
for (i = ; i < len; i++) {
up = ;
for (j = ; j < T.len; j++) {
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if (temp > MAXN) {
temp1 = temp - temp / (MAXN + ) * (MAXN + );
up = temp / (MAXN + );
ret.a[i + j] = temp1;
} else {
up = ;
ret.a[i + j] = temp;
}
}
if (up != )
ret.a[i + j] = up;
}
ret.len = i + j;
while (ret.a[ret.len - ] == && ret.len > )
ret.len--;
return ret;
} BigNum BigNum::operator/(const int &b) const { //大数对一个整数进行相除运算
BigNum ret;
int i, down = ;
for (i = len - ; i >= ; i--) {
ret.a[i] = (a[i] + down * (MAXN + )) / b;
down = a[i] + down * (MAXN + ) - ret.a[i] * b;
}
ret.len = len;
while (ret.a[ret.len - ] == && ret.len > )
ret.len--;
return ret;
} int BigNum::operator%(const int &b) const { //大数对一个int类型的变量进行取模运算
int i, d = ;
for (i = len - ; i >= ; i--) {
d = ((d * (MAXN + )) % b + a[i]) % b;
}
return d;
} BigNum BigNum::operator^(const int &n) const { //大数的n次方运算
BigNum t, ret();
int i;
if (n < )
exit(-);
if (n == )
return ;
if (n == )
return *this;
int m = n;
while (m > ) {
t = *this;
for (i = ; i << <= m; i <<= ) {
t = t * t;
}
m -= i;
ret = ret * t;
if (m == )
ret = ret * (*this);
}
return ret;
} bool BigNum::operator>(const BigNum &T) const { //大数和另一个大数的大小比较
int ln;
if (len > T.len)
return true;
else if (len == T.len) {
ln = len - ;
while (a[ln] == T.a[ln] && ln >= )
ln--;
if (ln >= && a[ln] > T.a[ln])
return true;
else
return false;
} else
return false;
} bool BigNum::operator>(const int &t) const { //大数和一个int类型的变量的大小比较
BigNum b(t);
return *this > b;
} void BigNum::print() { //输出大数
int i;
cout << a[len - ];
for (i = len - ; i >= ; i--) {
cout.width(DLEN);
cout.fill('');
cout << a[i];
}
//cout << endl;
}
int t, n;
int main() {
sf(t);
while(t--) {
sf(n);
BigNum temp = , ans = ;
for (int i = ; i <= n ; i++) temp = temp * i;
for (int i = ; i <= n ; i++) {
ans=ans+temp/i;
}
ans.print();
printf(".0\n");
}
return ;
}