首页 > ACM题库 > HDU-杭电 > HDU 3723-Delta Wave-递推-[解题报告]HOJ
2015
02-21

HDU 3723-Delta Wave-递推-[解题报告]HOJ

Delta Wave

问题描述 :

A delta wave is a high amplitude brain wave in humans with a frequency of 1 �C 4 hertz which can be recorded with an electroencephalogram (EEG) and is usually associated with slow-wave sleep (SWS).
– from Wikipedia

The researchers have discovered a new kind of species called "otaku", whose brain waves are rather strange. The delta wave of an otaku’s brain can be approximated by a polygonal line in the 2D coordinate system. The line is a route from point (0, 0) to (N, 0), and it is allowed to move only to the right (up, down or straight) at every step. And during the whole moving, it is not allowed to dip below the y = 0 axis.

For example, there are the 9 kinds of delta waves for N = 4:

Card Game

Given N, you are requested to find out how many kinds of different delta waves of otaku.

输入:

There are no more than 20 test cases. There is only one line for each case, containing an integer N (2 < N <= 10000)

输出:

There are no more than 20 test cases. There is only one line for each case, containing an integer N (2 < N <= 10000)

样例输入:

3
4

样例输出:

4
9

把向上看成+1,向下看成-1.可以知道符合卡特兰数的一般解释了。记作Can(i)

中间平过的即是0。亦即是C(n,2*i),i表示向上的数。

于是总的就是sum(C(n,2*i)*Can(i)),i从0至n/2。

注意,通项是可以通过递推求得的。

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;
import java.io.InputStreamReader;


public class Main{
        public static void main(String args[]){
        BigInteger B,C,D,E,ANS,TMP;
        int n,k;
        Scanner in=new Scanner(System.in);
	BigInteger MOD=BigInteger.ONE;
	TMP=BigInteger.TEN;
	for(int i=1;i<=100;i++)
		MOD=MOD.multiply(TMP);
        while(in.hasNext()){
            n=in.nextInt();
            k=n/2;
            ANS=BigInteger.ONE;
	TMP=BigInteger.ONE;
            for(int i=1;i<=k;i++){
                TMP=TMP.multiply(BigInteger.valueOf(n-2*i+2)).multiply(BigInteger.valueOf(n-2*i+1)).divide(BigInteger.valueOf(i)).divide(BigInteger.valueOf(i+1));
                ANS=ANS.add(TMP);
            }
            System.out.println(ANS.remainder(MOD));
        }
        }
}

  

参考:http://www.cnblogs.com/jie-dcai/p/4009718.html


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!