hdu 4927 组合+公式

http://acm.hdu.edu.cn/showproblem.php?pid=4927

给定一个长度为n的序列a，每次生成一个新的序列，长度为n-1，新序列b中bi=ai+1−ai,直到序列长度为1.输出最后的数。

n有3000果断用大数，类似杨辉三角推出每个数对最终结果的贡献，利用公式：c[n][m] = c[n][m-1]*(n-m+1)/m防超时

import java.math.BigInteger;

import java.util.*;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        int _ = cin.nextInt();

        BigInteger[] t = new BigInteger[3005];

        while(true)

        {

            if(_==0)

                break;

            _--;

            int n = cin.nextInt();

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

                t[i] = cin.nextBigInteger();

            BigInteger ans = BigInteger.ZERO;

            BigInteger s = BigInteger.ONE;

            int flag = n%2;

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

                if(i%2 == flag)

                    ans = ans.add(s.multiply(t[i]));

                else

                    ans = ans.subtract(s.multiply(t[i]));

                s = s.multiply(BigInteger.valueOf(n - i)).divide(BigInteger.valueOf(i));

            }

            System.out.println(ans);

        }

    }

}

巴特西

hdu 4927 组合+公式

最新文章

热门文章