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

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

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

 
 
 

日志

 
 

poj 2094  

2010-07-14 21:50:07|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目巨卡无比,没想到用差分序列,好思想,差分序列就是说给定一个n次多项式p(x),若已知p(x),p(x+1)....p(x+n)可以只用加减法推出p(x+n+1)首先第一行是n+1个值,第二行是第一行相邻两项相减的值,就是说是p(x+1)-p(x),p(x+2)-p(x+1).......第三行是第二行相邻两项相减的值,以此类推,直到最后就剩一个值,这样每次推下一个数时,从最后一行往上推即可
import java.math.*;
import java.util.*;

public class Main {
static BigInteger l, t;
static int m, n, k;
static BigInteger[] a = new BigInteger[15];
static BigInteger[][] q = new BigInteger[15][15];
static char[] c;
static char[] cc;

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
l = new BigInteger(in.next());
k = in.nextInt();
m = in.nextInt();
BigInteger w = BigInteger.TEN.pow(m);
for (int i = 0; i <= n; ++i)
a[i] = new BigInteger(in.next());
for (int i = 0; i < Math.min(k, n + 1); ++i) {
t = a[0];
for (int j = 1; j <= n; ++j) {
t = t.multiply(l);
t = t.add(a[j]);
}
t=t.mod(w);
q[n][i] = t.mod(w);
int ret = 0;
c = t.toString().toCharArray();
int ll = c.length;
for (int j = 0; j < Math.min(m, ll); ++j) {
ret += (c[ll - 1 - j] - '0') * (c[ll - 1 - j] - '0');
}
System.out.println(ret);
l = l.add(BigInteger.ONE);
}
if (k > n) {
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j <= i; j++)
q[i][j] = q[i + 1][j + 1].subtract(q[i + 1][j]).mod(w);
}
for(int i=1;i<=n;++i)
q[0][i]=q[0][0];
int po = 1;
for (int i = n + 1; i < k; ++i) {
for (int j = 1; j <= n; ++j)
q[j][(po + j) % (n + 1)] = q[j - 1][(po + j - 1) % (n + 1)]
.add(q[j][(po + j - 1) % (n + 1)]).mod(w);
int ret = 0;
c = q[n][(po + n) % (n + 1)].mod(w).toString().toCharArray();
int ll = c.length;
for (int j = 0; j < Math.min(m, ll); ++j) {
ret += (c[ll - 1 - j] - '0') * (c[ll - 1 - j] - '0');
}
System.out.println(ret);
l = l.add(BigInteger.ONE);
++po;
}
}
}
}
  评论这张
 
阅读(362)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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