成都赛B题,水得可以的,一刚开始公式不知道是不是自己故意的写错了,然后以为用java大数能AC的,就交给队友写,后来才发现要算到C(nn+k)当n很大的时候内存都受不了.然后在找个n=3p=0.4时的例子,发现公式错了,我去,已经两个半小时了.
还是用哥自创的科学计算法吧,O(n)的效率.
定义一个结构体记录两个数f(double)d(int),表示的数为f*10^d.f可以为这个数作缓冲,得到答案是将d调到0,其中的f就是答案了.
总的效率还是O(n),不用怕精度和效率不够了,哪怕数据范围再大十倍.
其实,用另外一个数学方法,也同样可以办到.那就对于p^(n+k),取对数(O(1)的效率).对于C(nn+k)根据上面的对推方法同样取对数然后累加,然后在用自然常数取幂,就可以得到答案.但是我不确定,那样得到的精度能不能给过,读者可以自己试试.