QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73383#4228. Double SortLinsheyAC ✓450ms40940kbC++1730.0kb2023-01-24 20:53:312023-01-24 20:53:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-24 20:53:35]
  • 评测
  • 测评结果:AC
  • 用时:450ms
  • 内存:40940kb
  • [2023-01-24 20:53:31]
  • 提交

answer


#include <bits/stdc++.h>

using namespace std; const int maxn = 51, maxm = 10001;

#define ACCURACY 1000; // 定义除法精度

namespace std
{
    // 定义除零错误
    class DividedByZeroException : std::exception
    {
    public:
        char const *what() const noexcept override
        {
            return "Divided By Zero Exception!";
        }
    };

    // 高精度浮点数类
    class WFloat
    {
        // 基本运算符重载
        friend WFloat operator+(const WFloat &, const WFloat &); // 加法重载
        friend WFloat operator-(const WFloat &, const WFloat &); // 减法重载
        friend WFloat operator*(const WFloat &, const WFloat &); // 乘法重载
        friend WFloat operator/(const WFloat &, const WFloat &); // 除法重载
        friend WFloat operator-(const WFloat &);                 // 负号重载

        // 比较重载
        friend bool operator==(const WFloat &, const WFloat &); // 等于重载
        friend bool operator!=(const WFloat &, const WFloat &); // 不等于重载
        friend bool operator<(const WFloat &, const WFloat &);  // 小于重载
        friend bool operator<=(const WFloat &, const WFloat &); // 小于等于重载
        friend bool operator>(const WFloat &, const WFloat &);  // 大于重载
        friend bool operator>=(const WFloat &, const WFloat &); // 大于等于重载

        // 扩展运算符重载
        friend WFloat operator+=(WFloat &, const WFloat &); // 加等重载
        friend WFloat operator-=(WFloat &, const WFloat &); // 减等重载
        friend WFloat operator*=(WFloat &, const WFloat &); // 乘等重载
        friend WFloat operator/=(WFloat &, const WFloat &); // 除等重载

        // 输入输出重载
        friend ostream &operator<<(ostream &, const WFloat &); // 输出重载
        friend istream &operator>>(istream &, WFloat &);       // 输入重载

    public:
        WFloat();
        WFloat(int);                          // 用一个整数构造
        WFloat(double);                       // 用一个浮点数构造
        WFloat(const string &);               // 用一个字符串构造
        WFloat(const WFloat &);               // 用一个高精度数构造
        WFloat(WFloat &&) noexcept;           // 移动构造
        WFloat operator=(const WFloat &);     // 赋值函数
        WFloat operator=(WFloat &&) noexcept; // 移动赋值

        WFloat abs() const; // 取绝对值
        ~WFloat() = default;

        static const WFloat &ZERO()
        {
            static WFloat zero{0};
            return zero;
        };

        static const WFloat &ONE()
        {
            static WFloat one{1};
            return one;
        };

        static const WFloat &TEN()
        {
            static WFloat ten{10};
            return ten;
        };

    #define WFLOAT_ZERO WFloat::ZERO()
    #define WFLOAT_ONE WFloat::ONE()
    #define WFLOAT_TEN WFloat::TEN()

    private:
        vector<char> integer; // 整数部分
        vector<char> decimal; // 小数部分
        void trim();          // 将多余的零删去
        bool tag;             // 用来表示正负,true为正
    };

    inline void WFloat::trim()
    {
        // 因为我们是逆向存储的,所以整数的尾部和小数的首部可能会有多余的0
        auto iter = integer.rbegin();

        // 对整数部分
        while (!integer.empty() && (*iter) == 0)
        {
            integer.pop_back();      // 指向不为空且尾部为0,删去
            iter = integer.rbegin(); // 再次指向尾部
                                    // 整数部分的“尾部”就是最高位,如00515.424900的左两个0
        }

        if (integer.size() == 0 && decimal.size() == 0) // 如果整数、小数全为空
        {
            tag = true;
        }

        if (integer.size() == 0) // 如果整数部分是0
        {
            integer.push_back(0);
        }

        auto it = decimal.begin();

        // 对小数部分
        while (!decimal.empty() && (*it) == 0)
        {
            it = decimal.erase(it); // 指向不为空且首部为0,删去
                                    // 小数部分的“首部”就是最低位,上例中的右两个0
        }

        if (decimal.size() == 0) // 如果小数部分是0
        {
            decimal.push_back(0);
        }
    }

    inline WFloat::WFloat() // 默认构造函数
    {
        tag = true;
        integer.push_back(0);
        decimal.push_back(0);
    }

    inline WFloat::WFloat(int num) // 用整型初始化
    {
        if (num >= 0) // 判断正负
        {
            tag = true;
        }
        else
        {
            tag = false;
            num *= (-1);
        }
        do
        {
            integer.push_back((char)(num % 10)); // 按位倒序写入整数部分
            num /= 10;
        } while (num != 0);

        decimal.push_back(0); // 因为用整数赋值,小数部分为0
    }

    inline WFloat::WFloat(double num)
    {
        *this = WFloat(std::to_string(num));
    }

    inline WFloat::WFloat(const string &num) // 用字符串初始化,格式形如"-123.456"、"1.0"
    {
        // 用于判断小数与整数部分交界
        bool type = num.find('.') == std::string::npos ? false : true;

        // 默认为正数,读到'-'再变为负数
        tag = true;

        // 逆向迭代
        for (auto iter = num.crbegin(); iter < num.crend(); iter++)
        {
            char ch = (*iter);
            if (ch == '.') // 遇到小数点则开始向整数部分写入
            {
                type = false;
                iter++;
            }
            if (iter == num.rend() - 1) // 读取正负号
            {
                if (ch == '+')
                {
                    break;
                }
                if (ch == '-')
                {
                    tag = false;
                    break;
                }
            }
            // 利用逆向迭代器,将整个数据倒序存入
            if (type)
                decimal.push_back((char)((*iter) - '0'));
            else
                integer.push_back((char)((*iter) - '0'));
        }
    }

    inline WFloat::WFloat(const WFloat &num) // 利用高精度类初始化
    {
        integer = num.integer;
        decimal = num.decimal;
        tag = num.tag;
    }

    inline WFloat::WFloat(WFloat &&num) noexcept // 移动构造
    {
        integer.swap(num.integer);
        decimal.swap(num.decimal);
        tag = num.tag;
    }

    inline WFloat WFloat::operator=(const WFloat &num) // 赋值(拷贝)操作
    {
        integer = num.integer;
        decimal = num.decimal;
        tag = num.tag;
        return (*this);
    }

    inline WFloat WFloat::operator=(WFloat &&num) noexcept
    {
        integer.swap(num.integer);
        decimal.swap(num.decimal);
        tag = num.tag;
        return *this;
    }

    inline WFloat WFloat::abs() const // 取绝对值
    {
        if (tag)
            return (*this);
        else
            return -(*this);
    }

    inline WFloat operator-(const WFloat &num) // 取负操作
    {
        WFloat temp(num);
        temp.tag = !temp.tag;
        return temp;
    }

    inline ostream &operator<<(ostream &out, const WFloat &num) // 输出重载
    {
        if (!num.tag) // 负数
        {
            out << "-";
        }

        for (auto iter = num.integer.rbegin(); iter != num.integer.rend(); iter++) // 输出整数部分
        {
            out << (char)((*iter) + '0');
        }

        out << '.';

        for (auto iter = num.decimal.rbegin(); iter != num.decimal.rend(); iter++) // 输出小数部分
        {
            out << (char)((*iter) + '0');
        }
        return out;
    }

    inline istream &operator>>(istream &in, WFloat &num) // 输入重载
    {
        string str;
        in >> str;
        num = WFloat(str);
        return in;
    }

    inline WFloat operator+=(WFloat &num1, const WFloat &num2) // 加等于重载
    {
        if (num1.tag == num2.tag) // 只处理同符号数,异号由-减法处理
        {
            vector<char>::iterator iter1;
            vector<char>::const_iterator iter2, it;

            //先处理小数部分
            int num1_decimal_size = num1.decimal.size(); // 小数部分长度
            int num2_decimal_size = num2.decimal.size();
            char carry = 0;                            // 进位
            if (num1_decimal_size < num2_decimal_size) // 如果num2小数部分更长
            {
                iter1 = num1.decimal.begin();
                iter2 = num2.decimal.begin();
                iter2 = iter2 - (num1_decimal_size - num2_decimal_size); // 将指向调整到一一对应的位置

                while (iter1 != num1.decimal.end() && iter2 != num2.decimal.end())
                {
                    (*iter1) = (*iter1) + (*iter2) + carry;
                    carry = ((*iter1) > 9); // 如果大于9则carry=1
                    (*iter1) = (*iter1) % 10;
                    iter1++;
                    iter2++;
                }

                it = num2.decimal.begin();
                iter2 = num2.decimal.end();
                iter2 = iter2 - num1_decimal_size - 1; // 指向长出部分
                while (iter2 != it)
                {
                    num1.decimal.insert(num1.decimal.begin(), *iter2);
                    iter2--;
                }
                num1.decimal.insert(num1.decimal.begin(), *iter2);
                iter1 = num1.decimal.begin();
            }
            else if (num1_decimal_size > num2_decimal_size) // 如果num1小数部分更长,同理
            {
                iter1 = num1.decimal.begin();
                iter1 = iter1 + (num1_decimal_size - num2_decimal_size);
                // 将指向调整到一一对应的位置
                iter2 = num2.decimal.begin();

                while (iter1 != num1.decimal.end() && iter2 != num2.decimal.end())
                {
                    (*iter1) = (*iter1) + (*iter2) + carry;
                    carry = ((*iter1) > 9); // 如果大于9则carry=1
                    (*iter1) = (*iter1) % 10;
                    iter1++;
                    iter2++;
                }
            }
            else
            {
                iter1 = num1.decimal.begin(); // 如果二者等长
                iter2 = num2.decimal.begin();
                while (iter1 != num1.decimal.end() && iter2 != num2.decimal.end())
                {
                    (*iter1) = (*iter1) + (*iter2) + carry;
                    carry = ((*iter1) > 9); // 如果大于9则carry=1
                    (*iter1) = (*iter1) % 10;
                    iter1++;
                    iter2++;
                }
            }

            // 再处理整数部分
            iter1 = num1.integer.begin();
            iter2 = num2.integer.begin();
            // 从个位开始相加
            while (iter1 != num1.integer.end() && iter2 != num2.integer.end())
            {
                (*iter1) = (*iter1) + (*iter2) + carry;
                carry = ((*iter1) > 9); // 如果大于9则carry=1
                (*iter1) = (*iter1) % 10;
                iter1++;
                iter2++;
            }
            // 总会有一个先到达end()
            while (iter1 != num1.integer.end()) // 如果被加数更长,处理进位
            {
                (*iter1) = (*iter1) + carry;
                carry = ((*iter1) > 9); // 如果大于9则carry=1
                (*iter1) = (*iter1) % 10;
                iter1++;
            }
            while (iter2 != num2.integer.end()) // 加数更长
            {
                char val = (*iter2) + carry;
                carry = (val > 9);
                val %= 10;
                num1.integer.push_back(val);
                iter2++;
            }
            if (carry != 0) // 如果还有进位,则说明要添加一位
            {
                num1.integer.push_back(carry);
            }
            num1.trim();
            return num1;
        }
        else
        {                 // 如果异号
            if (num1.tag) // 如果被加数为正,加数为负,相当于减等于
            {
                WFloat temp(-num2);
                return num1 -= temp;
            }
            else
            {
                WFloat temp(-num1);
                return num1 = num2 - temp;
            }
        }
    }

    inline WFloat operator-=(WFloat &num1, const WFloat &num2) // 减等于重载
    {
        if (num1.tag == num2.tag) // 只处理同号,异号由+加法处理
        {
            if (num1.tag) // 如果同为正
            {
                if (num1 < num2) // 且被减数小
                {
                    WFloat temp(num2 - num1);
                    num1 = -temp;
                    num1.trim();
                    return num1;
                }
            }
            else
            {
                if (-num1 > -num2) // 如果同为负,且被减数绝对值大
                    return num1 = -((-num1) - (-num2));
                else
                    return num1 = (-num2) - (-num1);
            }

            // 下面是同为正,且减数小的情况
            // 小数部分
            char borrow = 0; // 借位
            int num1_decimal_size = num1.decimal.size();
            int num2_decimal_size = num2.decimal.size();
            auto it1 = num1.decimal.begin();
            auto it2 = num2.decimal.begin();

            if (num1_decimal_size > num2_decimal_size) // 如果被减数小数部分更长
            {
                num1_decimal_size -= num2_decimal_size; // 长出部分
                it1 = it1 + num1_decimal_size;          // 跳过长出部分
            }
            else
            { // 如果减数的小数部分更长,则需要给被减数补0
                int number = num2_decimal_size - num1_decimal_size;
                while (number != 0)
                {
                    num1.decimal.insert(num1.decimal.begin(), 0); // 缺少的位数补0
                    number--;
                }
                it1 = num1.decimal.begin(); // 插入后需要重新指向
                it2 = num2.decimal.begin();
            }
            while ((it1 != num1.decimal.end()) && (it2 != num2.decimal.end()))
            {
                (*it1) = (*it1) - (*it2) - borrow;
                borrow = 0;
                if ((*it1) < 0)
                {
                    borrow = 1;
                    (*it1) += 10;
                }
                it1++;
                it2++;
            }
            // 整数部分
            auto iter1 = num1.integer.begin();
            auto iter2 = num2.integer.begin();

            while (iter1 != num1.integer.end() && iter2 != num2.integer.end())
            {
                (*iter1) = (*iter1) - (*iter2) - borrow;
                borrow = 0;
                if ((*iter1) < 0)
                {
                    borrow = 1;
                    (*iter1) += 10;
                }
                iter1++;
                iter2++;
            }
            while (iter1 != num1.integer.end())
            {
                (*iter1) = (*iter1) - borrow;
                borrow = 0;
                if ((*iter1) < 0)
                {
                    borrow = 1;
                    (*iter1) += 10;
                }
                else
                    break;
                iter1++;
            }
            num1.trim(); // 把多余的0去掉
            return num1;
        }
        else
        {
            // 如果异号
            if (num1 > WFLOAT_ZERO)
            {
                WFloat temp(-num2);
                return num1 += temp;
            }
            else
            {
                WFloat temp(-num1);
                return num1 = -(num2 + temp);
            }
        }
    }

    inline WFloat operator*=(WFloat &num1, const WFloat &num2) // 乘等于重载
    {
        WFloat result(0);                               // 储存结果
        if (num1 == WFLOAT_ZERO || num2 == WFLOAT_ZERO) // 有0做乘数得0
            result = WFLOAT_ZERO;
        else
        {
            int size = 0;
            vector<char> temp_num1(num1.integer.begin(), num1.integer.end());                           // 一个临时变量,用于将整数部分与小数部分合并
            if (num1.decimal.size() != 1 || (num1.decimal.size() == 1 && (*num1.decimal.begin()) != 0)) // 如果被乘数有小数部分,插入小数
            {
                temp_num1.insert(temp_num1.begin(), num1.decimal.begin(), num1.decimal.end());
                size += num1.decimal.size();
            }

            vector<char> temp_num2(num2.integer.begin(), num2.integer.end());                           // 一个临时变量,用于将整数部分与小数部分合并
            if (num2.decimal.size() != 1 || (num2.decimal.size() == 1 && (*num2.decimal.begin()) != 0)) // 如果被乘数有小数部分,插入小数
            {
                temp_num2.insert(temp_num2.begin(), num2.decimal.begin(), num2.decimal.end());
                size += num2.decimal.size();
            }

            // 开始乘法
            auto iter2 = temp_num2.begin();
            while (iter2 != temp_num2.end())
            {
                if (*iter2 != 0)
                {
                    deque<char> temp(temp_num1.begin(), temp_num1.end());
                    char carry = 0; // 进位
                    auto iter1 = temp.begin();
                    while (iter1 != temp.end()) // 被乘数乘以某一位乘数
                    {
                        (*iter1) *= (*iter2);
                        (*iter1) += carry;
                        carry = (*iter1) / 10;
                        (*iter1) %= 10;
                        iter1++;
                    }
                    if (carry != 0)
                    {
                        temp.push_back(carry);
                    }
                    int num_of_zeros = iter2 - temp_num2.begin(); // 计算错位
                    while (num_of_zeros--)
                        temp.push_front(0); // 乘得结果后面添0
                    WFloat temp2;
                    temp2.integer.clear();
                    temp2.integer.insert(temp2.integer.end(), temp.begin(), temp.end());
                    temp2.trim();
                    result = result + temp2;
                }
                iter2++;
            }
            result.tag = ((num1.tag && num2.tag) || (!num1.tag && !num2.tag));

            // 由于我们将小数和整数合并在一起,因此下面要把小数点重新添上
            if (size != 0)
            {
                if (size >= result.integer.size()) //说明需要补前导0
                {
                    int n = size - result.integer.size();
                    for (int i = 0; i <= n; i++)
                        result.integer.insert(result.integer.end(), 0);
                }
                result.decimal.clear();
                result.decimal.insert(result.decimal.begin(), result.integer.begin(), result.integer.begin() + size);
                result.integer.erase(result.integer.begin(), result.integer.begin() + size);
            }
        }
        num1 = result;
        num1.trim();
        return num1;
    }

    inline WFloat operator/=(WFloat &num1, const WFloat &num2) // 除等于重载
    {
        if (num2 == WFLOAT_ZERO)
            throw DividedByZeroException();
        if (num1 == WFLOAT_ZERO)
            return num1;
        if (num1 == num2)
            return (num1 = WFLOAT_ONE);

        WFloat temp_num1 = num1;
        WFloat temp_num2 = num2;

        // 转换成无符号除法来做
        temp_num1.tag = true;
        temp_num2.tag = true;

        int Integer_Size = 0; // 整数部分应为几位
        if ((temp_num2.decimal.size() == 1) && (*(temp_num2.decimal.begin()) == 0))
        {
            // 如果除数没有小数部分,不做操作
        }
        else
        {
            // 否则把除数和乘数同时扩大,直到除数为整数(只对Integer部分运算)
            int t = temp_num2.decimal.size();
            while (t--)
            {
                temp_num1 = temp_num1 * WFLOAT_TEN;
                temp_num2 = temp_num2 * WFLOAT_TEN;
            }
        }
        if (temp_num1 < temp_num2) // 被除数小于除数,应该是0.xxx
        {
            while (temp_num1 < temp_num2)
            {
                temp_num1 *= WFLOAT_TEN;
                Integer_Size--;
            }
        }
        else
        {
            while (temp_num1 > temp_num2)
            {
                temp_num1.decimal.push_back(*temp_num1.integer.begin());
                temp_num1.integer.erase(temp_num1.integer.begin());
                Integer_Size++;
            }
        }

        int k = ACCURACY;
        WFloat quotient(0); // 商

        while (k--)
        {
            if (temp_num1 < temp_num2)
            {
                temp_num1 = temp_num1 * WFLOAT_TEN;
                quotient = quotient * WFLOAT_TEN;
            }
            else
            {
                int i;
                WFloat compare;
                for (i = 1; i <= 10; i++) // “试商”
                {
                    WFloat BF(i);
                    compare = temp_num2 * BF;
                    if (compare > temp_num1)
                        break;
                }
                compare -= temp_num2;
                temp_num1 -= compare;
                WFloat index(i - 1);
                quotient = quotient + index;
            }
        }

        if (Integer_Size < 0) // 如果是小数除以大数,结果为0.xxx
        {
            vector<char> temp(quotient.integer.begin(), quotient.integer.end());
            quotient.integer.clear();
            quotient.integer.push_back(0); // 整数部分为0

            quotient.decimal.clear();
            int count_zero = -Integer_Size;
            // 下面先补充前导0
            while (--count_zero)
            {
                quotient.decimal.insert(quotient.decimal.begin(), 0);
            }
            quotient.decimal.insert(quotient.decimal.begin(), temp.begin(), temp.end());
        }
        else
        {
            if (quotient.integer.size() > Integer_Size)
            {
                vector<char> temp(quotient.integer.begin(), quotient.integer.end());

                quotient.integer.clear(); // 这里如果不清空会有错误

                quotient.integer.assign(temp.end() - Integer_Size, temp.end());

                quotient.decimal.clear(); // 同理需要清空

                quotient.decimal.insert(quotient.decimal.begin(), temp.begin(), temp.end() - Integer_Size);
            }
            else
            {
                // 这一部分意义不明,我觉得不会走到这个分支
                int t = Integer_Size - quotient.integer.size();
                while (t--)
                {
                    quotient = quotient * WFLOAT_TEN;
                }
            }
        }
        quotient.tag = ((num1.tag && num2.tag) || (!num1.tag && !num2.tag));
        num1 = quotient;
        num1.trim();
        return num1;
    }

    inline WFloat operator+(const WFloat &num1, const WFloat &num2) // 调用+=
    {
        WFloat temp(num1);
        temp += num2;
        return temp;
    }

    inline WFloat operator-(const WFloat &num1, const WFloat &num2) // 调用-=
    {
        WFloat temp(num1);
        temp -= num2;
        return temp;
    }

    inline WFloat operator*(const WFloat &num1, const WFloat &num2) // 调用*=
    {
        WFloat temp(num1);
        temp *= num2;
        return temp;
    }

    inline WFloat operator/(const WFloat &num1, const WFloat &num2) // 调用/=
    {
        WFloat temp(num1);
        temp /= num2;
        return temp;
    }

    inline bool operator<(const WFloat &num1, const WFloat &num2) // 小于重载
    {
        bool sign;                // 返回值
        if (num1.tag != num2.tag) // 如果异号
        {
            sign = !num1.tag; // 如果num1正,则不小于;反之,则小于
            return sign;
        }
        else
        {
            // 如果同号,先比较整数再比较小数
            if (num1.integer.size() != num2.integer.size()) // 如果整数部分不等长
            {
                if (num1.tag) // 如果同为正,则整数部分长的大
                {
                    sign = num1.integer.size() < num2.integer.size();
                    return sign;
                }
                else
                {
                    // 同为负,则整数部分长的小
                    sign = num1.integer.size() > num2.integer.size();
                    return sign;
                }
            }
            // 如果整数部分等长
            auto iter1 = num1.integer.rbegin();
            auto iter2 = num2.integer.rbegin();
            while (iter1 != num1.integer.rend())
            {
                if (num1.tag && *iter1 < *iter2)
                    return true;
                if (num1.tag && *iter1 > *iter2)
                    return false;
                if (!num1.tag && *iter1 > *iter2)
                    return true;
                if (!num1.tag && *iter1 < *iter2)
                    return false;
                iter1++;
                iter2++;
            }

            // 下面比较小数部分
            auto it1 = num1.decimal.rbegin();
            auto it2 = num2.decimal.rbegin();
            while (it1 != num1.decimal.rend() && it2 != num2.decimal.rend())
            {
                if (num1.tag && *it1 < *it2)
                    return true;
                if (num1.tag && *it1 > *it2)
                    return false;
                if (!num1.tag && *it1 > *it2)
                    return true;
                if (!num1.tag && *it1 < *it2)
                    return false;
                it1++;
                it2++;
            }
            // 如果整数部分,而小数部分停止前全部一样,那么看谁的小数位更多
            return (num1.tag && it2 != num2.decimal.rend()) || (!num1.tag && it1 != num1.decimal.rend());
        }
    }

    inline bool operator>(const WFloat &num1, const WFloat &num2) // 大于重载
    {
        bool tag = !(num1 <= num2);
        return tag;
    }

    inline bool operator==(const WFloat &num1, const WFloat &num2) // 等于重载
    {
        if (num1.tag != num2.tag)
            return false;
        if (num1.integer.size() != num2.integer.size())
            return false;
        if (num1.decimal.size() != num2.decimal.size())
            return false;

        // 如果长度和符号相同,那么下面逐位比较
        auto iter1 = num1.decimal.begin();
        auto iter2 = num2.decimal.begin();
        while (iter1 != num1.decimal.end())
        {
            if (*iter1 != *iter2)
                return false;
            iter1++;
            iter2++;
        }

        iter1 = num1.integer.begin();
        iter2 = num2.integer.begin();
        while (iter1 != num1.integer.end())
        {
            if (*iter1 != *iter2)
                return false;
            iter1++;
            iter2++;
        }
        return true;
    }

    inline bool operator!=(const WFloat &num1, const WFloat &num2)
    {
        return !(num1 == num2);
    }

    inline bool operator>=(const WFloat &num1, const WFloat &num2)
    {
        bool tag = (num1 > num2) || (num1 == num2);
        return tag;
    }

    inline bool operator<=(const WFloat &num1, const WFloat &num2)
    {
        bool tag = (num1 < num2) || (num1 == num2);
        return tag;
    }
}

const int H = 1e9;

inline void add(vector<int> &a, const vector<int> &b)
{
    while (a.size() < b.size()) a.push_back(0);
    int x = 0;
    int i;
    for (i = 0; i < b.size(); i++)
    {
        x += a[i] + b[i];
        if (x >= H) a[i] = x - H, x = 1;
        else a[i] = x, x = 0;
        assert(a[i] < H);
    }
    while (x && i < a.size())
    {
        x += a[i];
        if (x >= H) a[i] = x - H, x = 1;
        else a[i] = x, x = 0;
        assert(a[i] < H);
        i++;
    }
    if (x) a.push_back(1); 
}

inline WFloat trans(const vector<int> &a)
{
    WFloat res = 0;
    for (int i = int(a.size()) - 1; i >= 0; i--) res = res * H + a[i];
    return res;
}

vector<int> C[maxm][maxn]; WFloat C_[maxn][maxn];

int n, m;

WFloat tot, f[maxn];

WFloat Ans;

int main()
{
    for (int i = 0; i < maxm; i++)
    {
        C[i][0] = { 1 };
        for (int j = 1; j <= i && j < maxn; j++) C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
    }
    for (int i = 0; i < maxn; i++)
    {
        C_[i][0] = 1;
        for (int j = 1; j <= i && j < maxn; j++) C_[i][j] = C_[i - 1][j - 1] + C_[i - 1][j];
    }
    // cout << C_[50][25] << endl;
    // cout << trans(C[50][25]) << endl;
    // for (int x : C[50][25]) printf("%9d", x); cerr << endl;
    // return 0;
    cin >> n >> m;
    tot = trans(C[m][n]);
    // cout << tot << endl;
    for (int i = 1; i <= n; i++)
    {
        vector<int> now;
        for (int j = 0; m - i * j >= n; j++) add(now, C[m - i * j][n]);
        f[i] = trans(now) / tot;
        // cerr << f[i] << endl;
    }
    cout << setprecision(12);
    for (int k = n; k; k--)
    {
        for (int i = k; i <= n; i++)
        {
            Ans += f[i] * C_[i - 1][k - 1] * C_[n][i] * (i - k & 1 ? -1 : 1);
        }
        cout << Ans << endl;
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 69ms
memory: 40908kb

input:

3 5

output:

1.0
2.3
4.5

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 80ms
memory: 40940kb

input:

5 17

output:

1.1313833225597931480284421460892049127343244990303813833225597931480284421460892049127343244990303813833225597931480284421460892049127343244990303813833225597931480284421460892049127343244990303813833225597931480284421460892049127343244990303813833225597931480284421460892049127343244990303813833225...

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 450ms
memory: 40812kb

input:

50 10000

output:

4.4328164335364292488760188302673937541071340768261794745828633677688772961124888757027521574891753125757255154822248185653428735999294187669952485502432115650780818638215988678540513184559821345747418914469697989833158004248121026226551931846347698073126754509965460325939761118285772199990121307038...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 45ms
memory: 40752kb

input:

40 40

output:

1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
11.0
12.0
13.0
14.0
15.0
16.0
17.0
18.0
19.0
20.0
21.0
22.0
23.0
24.0
25.0
26.0
27.0
28.0
29.0
30.0
31.0
32.0
33.0
34.0
35.0
36.0
37.0
38.0
39.0
40.0

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 294ms
memory: 40852kb

input:

39 1489

output:

1.5270875628206370112493584533438324860200813024714339386699404305466181079268367800118460632294106355341649350450762086203874918904300963777337943572403434834944125782682307472120114971643613188195612218338439646388838563845035390896298308625940928690092572248253327771406884481946137558762941885059...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 428ms
memory: 40836kb

input:

47 9871

output:

4.8839175853662862782502975492935920993718824847882366755276400426114545234346544054470501784143472506941080704705744109373154641365238456844532498011531651728202314289053083731849330779506684759590785570732554320794542574826177782007853006910937380407876619654798899490292386252930497450328756113006...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 106ms
memory: 40876kb

input:

9 9999

output:

111.55622255525582866527807683056571565796794393840577677212370969932680385997466033889790337009972351984724305610123718258746162640352885614510365705775781672978310679390296963261302575510221181755890471387653996011693188781281574429756556451986986574207738112159458465896639278716059029017575612387...

result:

ok 9 numbers