题目链接:hdu 4927 Series 1
题目大意:给定一个长度为n的序列a,每次生成一个新的序列,长度为n-1,新序列b中bi=ai+1−ai,直到序列长度为1.输出最后的数。
解题思路:n最多才3000,ai最大也才1000,貌似不会超int,但是要注意,有些数不止被计算了一次,最多的数被计算了C(15003000),所以肯定要用高精度处理,那么用o(n2)的复杂度肯定就跪了。其实对于最后的ans,ans=∑i=0n−1C(in−1)∗ai∗(−1)i+1(类似杨辉三角)
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
BigInteger[] a;
a = new BigInteger[3005];
int cas, n;
cas = cin.nextInt();;
for (int k = 0; k < cas; k++) {
n = cin.nextInt();
for (int i = 0; i < n; i++)
a[i] = cin.nextBigInteger();
BigInteger ans = BigInteger.valueOf(0);
BigInteger c = BigInteger.valueOf(1);;
for (int i = 0; i < n; i++) {
BigInteger tmp = c.multiply(a[n-i-1]);
if (i%2 == 0)
ans = ans.add(tmp);
else
ans = ans.subtract(tmp);
tmp = c.multiply(BigInteger.valueOf(n-i-1));
c = tmp.divide(BigInteger.valueOf(i+1));
}
System.out.println(ans);
}
}
}
分享到:
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
hdu 1695 GCD(欧拉函数+容斥原理).docx
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241