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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 2515  

2010-08-01 22:42:07|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
差分序列这是很有意思的东西,设h(x)是关于x的多项式表达式,构造差分表,使得第一层为h(0),h(1)。。。,以后每层是上一层相邻两数的差
h(0) h(1) h(2) h(3)
h'(0) h'(1) h'(2)
h''(0) h''(1)
....................
称h(0),h'(0),h''(0)是0对角线,则有h(n)=c(n,0)*h(0)+c(n,1)*h‘(1)+。。。
且有sigma(h(n))=c(n+1,1)*h(0)+c(n+2,2)*h’(1)+。。。其中c(n,m)表示组合数,然后就可以求解了
import java.util.*;
import java.math.*;
public class Main {
static BigInteger solve(BigInteger n,int m){
BigInteger ret=BigInteger.ONE;
for(int i=0;i<m;++i){
ret=ret.multiply(n).divide(BigInteger.valueOf(i+1));
n=n.subtract(BigInteger.ONE);
}
return ret;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
BigInteger[][] h=new BigInteger[110][110];
for(int i=0;i<110;++i)
h[i]=new BigInteger[110];
int t=in.nextInt();
while(t-->0){
BigInteger n=in.nextBigInteger().add(BigInteger.ONE);
int m=in.nextInt();
for(int i=0;i<=m;++i)
h[0][i]=BigInteger.valueOf(i).pow(m);
for(int i=1;i<=m;++i)
for(int j=0;j<m+1-i;++j)
h[i][j]=h[i-1][j+1].subtract(h[i-1][j]);
BigInteger ans=BigInteger.ZERO;
for(int i=0;i<=m;++i)
ans=ans.add(h[i][0].multiply(solve(n,i+1)));
System.out.println(ans);
}
}

}
  评论这张
 
阅读(536)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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