hdu 4927グループ+公式

1298 ワード

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);
        }
    }
}