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タイムアウト防止
長い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);
}
}
}