递推,大数存储E - Order Count

时间:2023-03-08 17:53:35

Description

If we connect 3 numbers with "<" and "=", there are 13 cases: 
1) A=B=C 
2) A=B<C 
3) A<B=C 
4) A<B<C 
5) A<C<B 
6) A=C<B 
7) B<A=C 
8) B<A<C 
9) B<C<A 
10) B=C<A 
11) C<A=B 
12) C<A<B 
13) C<B<A

If we connect n numbers with "<" and "=", how many cases then?

Input

The input starts with a positive integer P(0<P<1000) which indicates the number of test cases. Then on the following P lines, each line consists of a positive integer n(1<=n<=50) which indicates the amount of numbers to be connected. 

Output

For each input n, you should output the amount of cases in a single line. 

Sample Input

2
1
3

Sample Output

1
13

Hint

Hint  Huge input, scanf is recommended.

source:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=95378#problem/E

参考博客:http://blog.****.net/acm_ted/article/details/7439043

这道题需要存储的数比较大,需要存下“500!”这么大的数,c或者c++的大数不会写,java提供大数类,直接用比较方便,我现在不会,就先写下思路,以后写题

问题:输入字母个数n,用大于小于等于号把这些字母连接起来的所有情况数
   注意(A = B > C)和(C < B = A)是一样的
思路:因为等于是相互的,算作一种情况,所以可以把所有相等的数分为一堆,看作一个字符
   这样就只剩下大于和小于号了
    由于 A > B和B < A也是一样的,所以我们可以假设只有大于号或者小于号
    然后把所有的数排列一下就行了

   由于分的堆的数目和每堆中的数据个数都是未知的,我们无法直接下手算i个字母连接的情况数
   但是我们可以通过递推,由前一种情况逐步找到要找的情况
   num[i][j]表示i个数分了j堆的连接数
   那么num[i][j] =        //注意最终形成了j堆, 不妨设所有的堆都是用小于号链接的
           num[i-1][j-1]*j
                  //最后一个数独立形成一堆,num[i-1][j-1]表示在最后一个数加入之前的排列数
                  //那么最后一个数加入的时候,就有j个位置可以选择,所以乘以j
           +num[i-1][j]*j;
                  //最后一个数和前面某一堆中的数据相等,加最后一个数之前的情况数为num[i-1][j]
                  //最后一个数入的堆可能是j堆中的任意一个,所以乘以j
   其实找到状态转义方程都好说num[i][j] = (num[i-1][j-1] + num[i-1][j])*j;
   初始化:num[i][j]为0;num[n][1]都为1
   

     f(1, 1) = 1
   f(2, 1) = 1, f(2, 2) = 2;
   f(3, 1) = 1, f(3, 2) = 6, f(3, 3) = 6;
   ……
   f(n, 1) = 1, ………………………………………………………………………………f(n, n) = A(n, n);
   因为我们假设符号已经排好, 就把这些数填进去就行,所以我们只需要算这些数放置的方法数即可
   除了f(i, 1) = 1; f(i, i) = A(i, i) (1 <= i <= n)之外,其他数都是按照我们推倒出来的公式计算的

   因为n可能为500这样我们就需要存储n的阶乘,需要大数运算,看网上有人用java的大数类直接存的,
   现在我还不会,先把思路了写下来,以后做