Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——C++的高精度真的是有太多技巧

Posted by fanhqme at 2009-08-25 18:35:31 on Problem 3742 and last updated at 2009-08-25 18:40:01
先说说这题怎么做。
设原多项式为f(x),新的为g(x),则
f(x)=g(x-2)
等价于
g(x)=f(x+2)
于是,只要用二项式定理,把(x+2)^k展开,乘上系数,统统相加就可以了。

不过,此题考的确是高精度计算...
同是高精度,人与人真的是有差别。

有一些技巧:预处理所有的组合数,预处理t的次方。

renew声称没有优化,因为这位大牛已经认为每个高精度数始终记录位数不是优化了。
也许可以冒昧的猜测renew学高精度时用的是一本比较正规的教材,
不是我所写的那个土鳖流高精度。

如果你和我一样懒,高精度时拒绝记录当前数一共有几位,也是可以AC的。
方法:
1.把所有的高精乘高精转换为高精乘以int
2.如果要连续乘16个2,那么只乘一次65536
3.如果要连续乘10个3,那么只乘一次59049
......
11.对于乘法操作,暂时计算一下高精度数的位数,乘的时候
只循环有效数字

用以上方法可以得到比直接套用renew的代码慢50%的速度,但是已经可以AC了!

大家快快来做这道题吧,我不想看到一共只有7个C++AC(其中一个还是我的小号),我还是垫底......


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator