Order Count
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 88 Accepted Submission(s): 5
Total Submission(s): 88 Accepted Submission(s): 5
Problem 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?
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.
SampleInput
2 1 3
SampleOutput
1 13
主要就是状态转移方程num[i][j]=(num[i-1][j-1]+num[i-1][j])*j
num[i][j]表示i个字母中有j个相等类(A=B<C=D,两个相等类(A=B和C=D))
解释:首先确定符号,因为“=”的前后互换是算作一种的,所以把“=”连在一起的当成一个字符,这样先确定符号的情况再往里面填字母(就是*j)
题目数据较大,需要用到高精度,偷懒用了java大数类。
import java.io.*; import java.util.*; import java.math.*; public class Main_AOJ440 { static BigInteger[][] num=new BigInteger[55][55]; public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); for(int i=0;i<=50;++i) for(int j=0;j<=50;++j) num[i][j]=BigInteger.ZERO; num[1][1]=BigInteger.valueOf(1); for(int i=2;i<=50;++i) for(int j=1;j<=i;++j) num[i][j]=num[i-1][j].add(num[i-1][j-1]).multiply(BigInteger.valueOf(j)); int temp=cin.nextInt(); for(;(temp--)!=0;) { int n=cin.nextInt(); BigInteger big=BigInteger.ZERO; for(int i=1;i<=n;i++) big=big.add(num[n][i]); System.out.println(big.toString()); } } }