欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51Nod-1836-战忽局的手段

程序员文章站 2022-07-02 14:50:31
...

ACM模版

描述

51Nod-1836-战忽局的手段

题解

这个题推导倒是很简单,关键是卡精度了,用 java 或者 py 都比较容易写,当然,用 C++__float128 也是可以的,但是不知道这个东西在比赛时是否可以正常使用。

这里提供了两个版本的代码,一个 C++ 版(代码 One)的,一个 Java 版(代码 Two)的。

代码

One:

#include <cstdio>

using namespace std;

__float128 QPow(__float128 x, long long p)
{
    __float128 ret = 1.0;
    while (p)
    {
        if (p & 1)
        {
            ret = ret * x;
        }
        x = x * x;
        p >>= 1;
    }

    return ret;
}

int T;
__float128 ans;
long long n, m;

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld%lld", &n, &m);
        ans = n - n * QPow((__float128)(n - 1) / n, m);
        printf("%.7f\n", (double)ans);
    }

    return 0;
}

Two:

import java.io.BufferedInputStream;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.Scanner;

public class Main {
    private static Scanner sc;

    public static BigDecimal QPow(BigDecimal a, long k) {
        BigDecimal res = BigDecimal.ONE;
        while (k != 0) {
            if ((k & 1) != 0) {
                res = res.multiply(a, MathContext.DECIMAL128);
            }
            a = a.multiply(a, MathContext.DECIMAL128);
            k >>= 1;
        }

        return res;
    }

    public static void main(String[] args) {
        sc = new Scanner(new BufferedInputStream(System.in));

        long n, k;
        int T = sc.nextInt();
        for (int i = 1; i <= T; i++) {
            n = sc.nextLong();
            k = sc.nextLong();
            BigDecimal a = BigDecimal.valueOf(n), ans;
            a = BigDecimal.ONE.divide(a, MathContext.DECIMAL128).negate().add(BigDecimal.ONE);
            ans = QPow(a, k).negate().add(BigDecimal.ONE, MathContext.DECIMAL128);
            ans = ans.divide(BigDecimal.ONE.subtract(a, MathContext.DECIMAL128), MathContext.DECIMAL128);
            System.out.println(ans);
        }
    }
}