HDU 3723 Delta Wave (高精度+calelan数)

题意：给定一个图，问你只能向上向下，或者平着走，有多少种方法可以走到最后一个格。

析：首先先考虑，如果没有平的情况就是calelan数了，现在有平的情况，那么就枚举呗，因为数很大，所以要用高精度。

答案应该是sum(C(n, 2*i)*C(n, i)/(i+1)) = a1 + a2 + a3 + ....，然后可以再化简一下，成为一个递推式ai = ai-1 * (n-2*i+1)*(n-2*i+2)/(k*(k+1))；

这次用记事本写的，然后没有测试，直接交的，虽然CE了一发，但还是挺好的。

代码如下：

import java.util.*;

import java.math.BigInteger;

public class Main{

    public static void main(String[] args){

        Scanner cin = new Scanner(System.in);

	BigInteger mod = BigInteger.TEN.pow(100);

	while(cin.hasNext()){

            int n = cin.nextInt();

	    BigInteger ans = BigInteger.ONE;

	    BigInteger x = BigInteger.ONE;

	    for(int i = 1; i + i <= n; ++i){

		x = x.multiply(BigInteger.valueOf((n-2*i+1)*(n-2*i+2))).divide(BigInteger.valueOf(i*(i+1)));

		ans = ans.add(x);

	    }

	    System.out.println(ans.mod(mod));

	}

    }

}

巴特西

HDU 3723 Delta Wave (高精度+calelan数)

最新文章

热门文章