G

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

Sample Outpu1.0

3.0
274.0
1026576.0


队友推出公式为
ans = n * ( 1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n );
看到n比较大 然后我就直接上大数了

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <set>
  7 #include <iostream>
  8 #include <map>
  9 #include <stack>
 10 #include <string>
 11 #include <vector>
 12 #define  pi acos(-1.0)
 13 #define  eps 1e-6
 14 #define  fi first
 15 #define  se second
 16 #define  lson l,m,rt<<1
 17 #define  rson m+1,r,rt<<1|1
 18 #define  bug         printf("******
")
 19 #define  mem(a,b)    memset(a,b,sizeof(a))
 20 #define  fuck(x)     cout<<"["<<x<<"]"<<endl
 21 #define  f(a)        a*a
 22 #define  sf(n)       scanf("%d", &n)
 23 #define  sff(a,b)    scanf("%d %d", &a, &b)
 24 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
 25 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
 26 #define  pf          printf
 27 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
 28 #define  FREE(i,a,b) for(i = a; i >= b; i--)
 29 #define  FRL(i,a,b)  for(i = a; i < b; i++)
 30 #define  FRLL(i,a,b) for(i = a; i > b; i--)
 31 #define  FIN         freopen("DATA.txt","r",stdin)
 32 #define  gcd(a,b)    __gcd(a,b)
 33 #define  lowbit(x)   x&-x
 34 #pragma  comment (linker,"/STACK:102400000,102400000")
 35 using namespace std;
 36 typedef long long  LL;
 37 const int INF = 0x7fffffff;
 38 const int mod = 1e9 + 7;
 39 const int maxn = 1e5 + 10;
 40 #define MAXN 9999
 41 #define MAXSIZE 10
 42 #define DLEN 4
 43 class BigNum {
 44 private:
 45     int a[(int)1e4 + 2000];  //可以控制大数的位数
 46     int len;       //大数长度
 47 public:
 48     BigNum() {
 49         len = 1;
 50         memset(a, 0, sizeof(a));
 51     }   //构造函数
 52     BigNum(const int);       //将一个int类型的变量转化为大数
 53     BigNum(const char *);     //将一个字符串类型的变量转化为大数
 54     BigNum(const BigNum &);  //拷贝构造函数
 55     BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算
 56 
 57     friend istream &operator>>(istream &, BigNum &);   //重载输入运算符
 58     friend ostream &operator<<(ostream &, BigNum &);   //重载输出运算符
 59 
 60     BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算
 61     BigNum operator-(const BigNum &) const;   //重载减法运算符，两个大数之间的相减运算
 62     BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算
 63     BigNum operator/(const int &) const;    //重载除法运算符，大数对一个整数进行相除运算
 64 
 65     BigNum operator^(const int &) const;    //大数的n次方运算
 66     int operator%(const int &) const;    //大数对一个int类型的变量进行取模运算
 67     bool operator>(const BigNum &T) const;   //大数和另一个大数的大小比较
 68     bool operator>(const int &t) const;      //大数和一个int类型的变量的大小比较
 69 
 70     void print();       //输出大数
 71 };
 72 
 73 BigNum::BigNum(const int b) {   //将一个int类型的变量转化为大数
 74     int c, d = b;
 75     len = 0;
 76     memset(a, 0, sizeof(a));
 77     while (d > MAXN) {
 78         c = d - (d / (MAXN + 1)) * (MAXN + 1);
 79         d = d / (MAXN + 1);
 80         a[len++] = c;
 81     }
 82     a[len++] = d;
 83 }
 84 
 85 BigNum::BigNum(const char *s) {   //将一个字符串类型的变量转化为大数
 86     int t, k, index, l, i;
 87     memset(a, 0, sizeof(a));
 88     l = strlen(s);
 89     len = l / DLEN;
 90     if (l % DLEN)
 91         len++;
 92     index = 0;
 93     for (i = l - 1; i >= 0; i -= DLEN) {
 94         t = 0;
 95         k = i - DLEN + 1;
 96         if (k < 0)
 97             k = 0;
 98         for (int j = k; j <= i; j++)
 99             t = t * 10 + s[j] - '0';
100         a[index++] = t;
101     }
102 }
103 
104 BigNum::BigNum(const BigNum &T) : len(T.len) { //拷贝构造函数
105     int i;
106     memset(a, 0, sizeof(a));
107     for (i = 0; i < len; i++)
108         a[i] = T.a[i];
109 }
110 
111 BigNum &BigNum::operator=(const BigNum &n) { //重载赋值运算符，大数之间进行赋值运算
112     int i;
113     len = n.len;
114     memset(a, 0, sizeof(a));
115     for (i = 0; i < len; i++)
116         a[i] = n.a[i];
117     return *this;
118 }
119 
120 istream &operator>>(istream &in, BigNum &b) { //重载输入运算符
121     char ch[MAXSIZE * 4];
122     int i = -1;
123     in >> ch;
124     int l = strlen(ch);
125     int count = 0, sum = 0;
126     for (i = l - 1; i >= 0;) {
127         sum = 0;
128         int t = 1;
129         for (int j = 0; j < 4 && i >= 0; j++, i--, t *= 10) {
130             sum += (ch[i] - '0') * t;
131         }
132         b.a[count] = sum;
133         count++;
134     }
135     b.len = count++;
136     return in;
137 
138 }
139 
140 ostream &operator<<(ostream &out, BigNum &b) { //重载输出运算符
141     int i;
142     cout << b.a[b.len - 1];
143     for (i = b.len - 2; i >= 0; i--) {
144         cout.width(DLEN);
145         cout.fill('0');
146         cout << b.a[i];
147     }
148     return out;
149 }
150 
151 BigNum BigNum::operator+(const BigNum &T) const { //两个大数之间的相加运算
152     BigNum t(*this);
153     int i, big;      //位数
154     big = T.len > len ? T.len : len;
155     for (i = 0; i < big; i++) {
156         t.a[i] += T.a[i];
157         if (t.a[i] > MAXN) {
158             t.a[i + 1]++;
159             t.a[i] -= MAXN + 1;
160         }
161     }
162     if (t.a[big] != 0)
163         t.len = big + 1;
164     else
165         t.len = big;
166     return t;
167 }
168 
169 BigNum BigNum::operator-(const BigNum &T) const { //两个大数之间的相减运算
170     int i, j, big;
171     bool flag;
172     BigNum t1, t2;
173     if (*this > T) {
174         t1 = *this;
175         t2 = T;
176         flag = 0;
177     } else {
178         t1 = T;
179         t2 = *this;
180         flag = 1;
181     }
182     big = t1.len;
183     for (i = 0; i < big; i++) {
184         if (t1.a[i] < t2.a[i]) {
185             j = i + 1;
186             while (t1.a[j] == 0)
187                 j++;
188             t1.a[j--]--;
189             while (j > i)
190                 t1.a[j--] += MAXN;
191             t1.a[i] += MAXN + 1 - t2.a[i];
192         } else
193             t1.a[i] -= t2.a[i];
194     }
195     t1.len = big;
196     while (t1.a[t1.len - 1] == 0 && t1.len > 1) {
197         t1.len--;
198         big--;
199     }
200     if (flag)
201         t1.a[big - 1] = 0 - t1.a[big - 1];
202     return t1;
203 }
204 
205 BigNum BigNum::operator*(const BigNum &T) const { //两个大数之间的相乘运算
206     BigNum ret;
207     int i, j, up;
208     int temp, temp1;
209     for (i = 0; i < len; i++) {
210         up = 0;
211         for (j = 0; j < T.len; j++) {
212             temp = a[i] * T.a[j] + ret.a[i + j] + up;
213             if (temp > MAXN) {
214                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
215                 up = temp / (MAXN + 1);
216                 ret.a[i + j] = temp1;
217             } else {
218                 up = 0;
219                 ret.a[i + j] = temp;
220             }
221         }
222         if (up != 0)
223             ret.a[i + j] = up;
224     }
225     ret.len = i + j;
226     while (ret.a[ret.len - 1] == 0 && ret.len > 1)
227         ret.len--;
228     return ret;
229 }
230 
231 BigNum BigNum::operator/(const int &b) const { //大数对一个整数进行相除运算
232     BigNum ret;
233     int i, down = 0;
234     for (i = len - 1; i >= 0; i--) {
235         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
236         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
237     }
238     ret.len = len;
239     while (ret.a[ret.len - 1] == 0 && ret.len > 1)
240         ret.len--;
241     return ret;
242 }
243 
244 int BigNum::operator%(const int &b) const {  //大数对一个int类型的变量进行取模运算
245     int i, d = 0;
246     for (i = len - 1; i >= 0; i--) {
247         d = ((d * (MAXN + 1)) % b + a[i]) % b;
248     }
249     return d;
250 }
251 
252 BigNum BigNum::operator^(const int &n) const {  //大数的n次方运算
253     BigNum t, ret(1);
254     int i;
255     if (n < 0)
256         exit(-1);
257     if (n == 0)
258         return 1;
259     if (n == 1)
260         return *this;
261     int m = n;
262     while (m > 1) {
263         t = *this;
264         for (i = 1; i << 1 <= m; i <<= 1) {
265             t = t * t;
266         }
267         m -= i;
268         ret = ret * t;
269         if (m == 1)
270             ret = ret * (*this);
271     }
272     return ret;
273 }
274 
275 bool BigNum::operator>(const BigNum &T) const { //大数和另一个大数的大小比较
276     int ln;
277     if (len > T.len)
278         return true;
279     else if (len == T.len) {
280         ln = len - 1;
281         while (a[ln] == T.a[ln] && ln >= 0)
282             ln--;
283         if (ln >= 0 && a[ln] > T.a[ln])
284             return true;
285         else
286             return false;
287     } else
288         return false;
289 }
290 
291 bool BigNum::operator>(const int &t) const {  //大数和一个int类型的变量的大小比较
292     BigNum b(t);
293     return *this > b;
294 }
295 
296 void BigNum::print() {  //输出大数
297     int i;
298     cout << a[len - 1];
299     for (i = len - 2; i >= 0; i--) {
300         cout.width(DLEN);
301         cout.fill('0');
302         cout << a[i];
303     }
304     //cout << endl;
305 }
306 int t, n;
307 int main() {
308     sf(t);
309     while(t--) {
310         sf(n);
311         BigNum temp = 1, ans = 0;
312         for (int i = 1 ; i <= n ; i++) temp = temp * i;
313         for (int i = 1 ; i <= n ; i++) {
314             ans=ans+temp/i;
315         }
316         ans.print();
317         printf(".0
");
318     }
319     return 0;
320 }