注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4927 Series 1  

2014-08-07 17:22:37|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4927
多校合练第6场1007。
题意:给n个数的A序列,按公式得到B序列,不断计算最后得到一个数,输出这个数。
题解:
通过简单推算,可以得到最后数的公式:
(An) - a1*(An-1)+a2*(An-2)-……
其中a1,a2,a3……这些系数是杨辉三角的值。
因为n最大3000,直接算肯定会超范围,所以用Java处理。
有个地方需要预处理下,用公式预处理出所有n的组合数:c(m,i)=c(m,i-1)*(m-i+1)/i。

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
public static void main( String args[] )
{
Scanner reader = new Scanner( System.in );
int f[]=new int[3010];
BigInteger c[]=new BigInteger[3010];
int n,T;
T=reader.nextInt();
for(int t=0;t<T;t++)
{
n = reader.nextInt();
for(int i=n-1;i>=0;i--)
f[i]=reader.nextInt();
c[0]=BigInteger.ONE;
c[1]=BigInteger.valueOf(n-1);
int nn=n-1;
for(int i=2;i<=nn;i++)
{
if(nn-i < i)
{
c[i]=c[nn-i];
continue;
}
c[i]=c[i-1].multiply(BigInteger.valueOf(nn-i+1));
c[i]=c[i].divide(BigInteger.valueOf(i));
}
BigInteger ans=BigInteger.ZERO;
int pos=1;
for(int i=0;i<n;i++)
{
int cnt=pos*f[i];
BigInteger ttt=c[i].multiply(BigInteger.valueOf(cnt));
ans=ans.add(ttt);
pos=pos*(-1);
}
System.out.println(ans);
}
}
}


  评论这张
 
阅读(75)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017