50分，求助

JjHh @ 2024-05-22 21:56:52

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int n;
LL res;
int main() {
    cin >> n;
    LL f = 1;
    for (int i = 1; i <= n; i++) {
        f *= i;
        res += f;
    }
    cout << res ;
    return 0;
}

by OIerWu_829 @ 2024-05-22 22:05:24

@JjHh 看 tag，高精度。

by qazsedcrfvgyhnujijn @ 2024-05-22 22:40:12

高精度
不嫌麻烦可以写一个高精度类，重载一堆运算符之后再做这道题
比如（当然其中很多用不到）：

//无敌高精度板子（牛顿迭代+位压+开根+FFT+倍增除法+手动分配空间）
//支持高精加，高精减，高精乘（普通），高精乘（FFT），高精除，高精模，高精快速幂，高精取模快速幂，高精开根，高精abs,高精相反数
#ifndef BIGINTEGER_H
#define BIGINTEGER_H

#include <cmath>
#include <vector>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <algorithm>

class BigInteger {
protected:
    using digit_t = long long;

    static const int WIDTH = 9;
    static const digit_t BASE = 1e9;
    static const long long FFT_LIMIT = 10000;

    digit_t* digits;
    long capacity, size;
    bool flag;

    inline void push(const digit_t&);
    inline void pop();

    inline int compare(const BigInteger&) const;

    static inline BigInteger fft_mul(const BigInteger&, const BigInteger&);
    inline BigInteger move(const long long&);
    static inline BigInteger inverse(const BigInteger&);

public:
    inline void reserve(const long&);

protected:
    inline void resize(const long&);

public:
    BigInteger() : digits(nullptr), flag(true) {*this = 0;}

    BigInteger(const BigInteger& x) : digits(nullptr) {*this = x;}
    BigInteger(const long long& x) : digits(nullptr) {*this = x;}
    BigInteger(const std::string& s) : digits(nullptr) {*this = s;}

    BigInteger& operator= (const BigInteger&);
    BigInteger& operator= (const long long&);
    BigInteger& operator= (const std::string&);

    ~BigInteger() {
        if (digits != nullptr) delete[] digits, digits = nullptr;
    }

    friend std::ostream& operator << (std::ostream& out, const BigInteger& x) {
        if (!x.flag) out << '-';
        out << (long long) x.digits[x.size];
        for (int i = x.size - 1; i >= 1; i--) 
            out << std::setw(WIDTH) << std::setfill('0') << (long long) x.digits[i];
        return out;
    }
    friend std::istream& operator >> (std::istream& in, BigInteger& x) {
        std::string s; in >> s; x = s; 
        return in;
    }

    std::string to_string() const;

    BigInteger operator- () const;
    BigInteger abs() const;

    bool operator< (const BigInteger&) const;
    bool operator> (const BigInteger&) const; 
    bool operator== (const BigInteger&) const; 
    bool operator!= (const BigInteger&) const;
    bool operator<= (const BigInteger&) const;
    bool operator>= (const BigInteger&) const;

    BigInteger operator+ (const BigInteger&) const;
    BigInteger operator- (const BigInteger&) const;
    BigInteger operator* (const BigInteger&) const;
    BigInteger operator/ (const long long&) const;
    BigInteger operator/ (const BigInteger&) const;
    BigInteger operator% (const long long&) const;
    BigInteger operator% (const BigInteger&) const;

    BigInteger pow(const long long&) const;
    BigInteger pow(const long long&, const BigInteger&) const;

    BigInteger sqrt(const long long& = 2) const;

    BigInteger& operator+= (const BigInteger&);
    BigInteger& operator-= (const BigInteger&);
    BigInteger& operator*= (const BigInteger&);
    BigInteger& operator/= (const long long&);
    BigInteger& operator/= (const BigInteger&);
    BigInteger& operator%= (const long long&);
    BigInteger& operator%= (const BigInteger&);
};

inline void BigInteger::push(const digit_t& val) {
    if (capacity == size) {
        long new_capacity = 0;
        if (capacity < 1000) new_capacity = capacity << 1;
        else new_capacity = (new_capacity >> 1) * 3;
        digit_t* new_digits = new digit_t[new_capacity + 1];
        std::memcpy(new_digits, digits, sizeof(long long) * (capacity + 1));
        delete[] digits;
        digits = new_digits, capacity = new_capacity, ++size;
        return;
    }
    digits[++size] = val;
}
inline void BigInteger::pop() {digits[size--] = 0;}

inline int BigInteger::compare(const BigInteger& x) const {
    if (flag && !x.flag) return 1;
    if (!flag && x.flag) return -1;

    int sgn = (flag && x.flag ? 1 : -1);
    if (size > x.size) return sgn;
    if (size < x.size) return -sgn;

    for (int i = size; i >= 1; i--) {
        if (digits[i] > x.digits[i]) return sgn;
        if (digits[i] < x.digits[i]) return -sgn;
    }
    return 0;
}

inline void BigInteger::reserve(const long& sz) {
    if (digits != nullptr) delete[] digits;
    capacity = sz, size = 0;
    digits = new digit_t[sz + 1];
    std::memset(digits, 0, sizeof(digit_t) * (sz + 1));
}
inline void BigInteger::resize(const long& sz) {
    reserve(sz), size = sz;
}

BigInteger& BigInteger::operator= (const BigInteger& x) {
    reserve(x.size + 1);
    flag = x.flag, size = x.size;
    std::memcpy(digits, x.digits, sizeof(digit_t) * (x.size + 1));
    return *this;
}
BigInteger& BigInteger::operator= (const long long& x) {
    flag = x >= 0;
    reserve(12);
    if (x == 0) {
        digits[1] = 0;
        return *this;
    }
    if (x == LLONG_MIN) return *this = "-9223372036854775808";
    long long n = std::abs(x);
    do {
        push(n % BASE);
        n /= BASE;
    } while (n);
    return *this;
}
BigInteger& BigInteger::operator= (const std::string& s) {
    flag = true, reserve(s.size() / WIDTH + 1);
    if (s.empty() || s == "-") return *this = 0;
    int i = 0;
    if (s[0] == '-') flag = false, i++;
    for (int j = s.size() - 1; j >= i; j -= WIDTH) {
        int start = std::max(i, j - WIDTH + 1), len = j - start + 1;
        push(std::stoi(s.substr(start, len)));
    }
    return *this;
}

std::string BigInteger::to_string() const {
    std::stringstream ss; ss << *this;
    return ss.str();
}

BigInteger BigInteger::operator- () const {
    BigInteger res = *this;
    res.flag = !flag;
    return res;
}
BigInteger BigInteger::abs() const {
    BigInteger res = *this;
    res.flag = true;
    return res;
}

bool BigInteger::operator< (const BigInteger& x) const {return compare(x) < 0;}
bool BigInteger::operator> (const BigInteger& x) const {return compare(x) > 0;}
bool BigInteger::operator== (const BigInteger& x) const {return compare(x) == 0;}
bool BigInteger::operator!= (const BigInteger& x) const {return compare(x) != 0;}
bool BigInteger::operator<= (const BigInteger& x) const {return compare(x) <= 0;}
bool BigInteger::operator>= (const BigInteger& x) const {return compare(x) >= 0;}

BigInteger BigInteger::operator+ (const BigInteger& x) const {
    if (!x.flag) return *this - x.abs();
    if (!flag) return x - abs();

    BigInteger res; 
    res.flag = !(flag ^ x.flag);
    int n = std::max(size, x.size) + 1;
    res.reserve(n);
    digit_t carry = 0;
    for (int i = 1; i <= n; i++) {
        digit_t d1 = i <= size ? digits[i] : 0, d2 = i <= x.size ? x.digits[i] : 0;
        res.push(d1 + d2 + carry);
        carry = res.digits[i] / BASE;
        res.digits[i] %= BASE;
    }
    while (res.size > 1 && res.digits[res.size] == 0) res.pop();
    return res;
}
BigInteger BigInteger::operator- (const BigInteger& x) const {
    if (!x.flag) return *this + x.abs();
    if (!flag) return -(abs() + x);
    BigInteger res;
    if (*this < x) res.flag = false;
    digit_t carry = 0;
    int n = std::max(size, x.size);
    res.reserve(n);
    for (int i = 1; i <= n; i++) {
        digit_t d1 = i <= size ? digits[i] : 0, d2 = i <= x.size ? x.digits[i] : 0;
        if (res.flag) res.push(d1 - d2 - carry);
        else res.push(d2 - d1 - carry);
        if (res.digits[i] < 0) res.digits[i] += BASE, carry = 1;
        else carry = 0;
    }
    while (res.size > 1 && res.digits[res.size] == 0) res.pop();
    return res;
}

namespace BigInteger_FFT {
    constexpr long double PI = std::acos(-1.0L);

    struct complex {
        long double real, imag;

        complex(long double x = 0.0, long double y = 0.0) : real(x), imag(y) {}

        complex operator + (const complex& other) const {
            return complex(real + other.real, imag + other.imag);
        }
        complex operator - (const complex& other) const {
            return complex(real - other.real, imag - other.imag);
        }
        complex operator * (const complex& other) const {
            return complex(real * other.real - imag * other.imag, real * other.imag + other.real * imag);
        }
        complex conj() const {
            return complex(real, -imag);
        }
    };

    complex* arr = nullptr;

    inline void init(int n) {
        if (arr != nullptr) delete[] arr, arr = nullptr;
        arr = new complex[n + 1];
        for (int i = 0; i <= n; i++) arr[i] = complex(0.0, 0.0);
    }

    inline void fft(complex* a, long len) {
        for (long i = len; i >= 2; i >>= 1) {
            complex wn(std::cos(2.0L * PI / i), std::sin(2.0L * PI / i));
            for (long j = 0; j < len; j += i) {
                complex w(1.0, 0.0);
                for (long k = j; k < j + (i >> 1); k++, w = w * wn) {
                    complex u = a[k], t = a[k + (i >> 1)];
                    a[k] = u + t, a[k + (i >> 1)] = w * (u - t);
                }
            }
        }
    }
    inline void idft(complex* a, long len) {
        for (long i = 2; i <= len; i <<= 1) {
            complex wn(std::cos(2.0L * PI / i), std::sin(2.0L * PI / i));
            for (long j = 0; j < len; j += i) {
                complex w(1.0, 0.0);
                for (long k = j; k < j + (i >> 1); k++, w = w * wn) {
                    complex u = a[k], t = w * a[k + (i >> 1)];
                    a[k] = u + t, a[k + (i >> 1)] = u - t;
                }
            }
        }
    }
}

BigInteger BigInteger::fft_mul(const BigInteger& a, const BigInteger& b) {
    long lim = 1;
    while (lim <= 3 * (a.size + b.size)) lim <<= 1;
    BigInteger_FFT::init(lim);
    using BigInteger_FFT::arr;
    for (int i = 0; i < a.size; i++) {
        arr[i * 3].real = a.digits[i + 1] % 1000;
        arr[i * 3 + 1].real = a.digits[i + 1] / 1000 % 1000;
        arr[i * 3 + 2].real = a.digits[i + 1] / (1000 * 1000);
    }
    for (int i = 0; i < b.size; i++) {
        arr[i * 3].imag = b.digits[i + 1] % 1000;
        arr[i * 3 + 1].imag = b.digits[i + 1] / 1000 % 1000;
        arr[i * 3 + 2].imag = b.digits[i + 1] / (1000 * 1000);
    }
    BigInteger_FFT::fft(arr, lim);
    for (int i = 0; i < lim; i++) arr[i] = (arr[i] * arr[i]).conj();
    BigInteger_FFT::idft(arr, lim);
    BigInteger res;
    res.resize(a.size + b.size + 1);
    digit_t carry = 0;
    for (int i = 0; i <= a.size + b.size; i++) {
        carry += (digit_t)(arr[i * 3].imag * -0.5 / lim + 0.5);
        carry += (digit_t)(arr[i * 3 + 1].imag * -0.5 / lim + 0.5) * 1000LL;
        carry += (digit_t)(arr[i * 3 + 2].imag * -0.5 / lim + 0.5) * 1000LL * 1000LL;
        res.digits[i + 1] += carry % BASE, carry /= BASE;
    }
    while (res.size > 1 && res.digits[res.size] == 0) res.pop();
    return res;
} 

BigInteger BigInteger::operator* (const BigInteger& x) const {
    BigInteger zero = 0;
    if (*this == zero || x == zero) return zero;
    int n = size, m = x.size;
    if (1LL * n * m >= 1) {
        BigInteger res = fft_mul(*this, x);
        res.flag = !(flag ^ x.flag);
        return res;
    }

    BigInteger res;
    res.flag = !(flag ^ x.flag);
    res.resize(n + m + 2);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            res.digits[i + j - 1] += digits[i] * x.digits[j];
            res.digits[i + j] += res.digits[i + j - 1] / BASE;
            res.digits[i + j - 1] %= BASE;
        }
    }
    for (int i = 1; i <= n + m + 1; i++) {
        res.digits[i + 1] += res.digits[i] / BASE;
        res.digits[i] %= BASE;
    }
    while (res.size > 1 && res.digits[res.size] == 0) res.pop();
    return res;
}

BigInteger BigInteger::operator/ (const long long& x) const {
    if (x == 0) throw -1;
    if (*this == 0) return 0;
    BigInteger res;
    res.flag = !(flag ^ (x >= 0));

    digit_t cur = 0, div = std::abs(x);
    res.resize(size);

    for (int i = size; i >= 1; i--) {
        cur = cur * BASE + digits[i];
        res.digits[i] = res.flag ? (cur / div) : (-cur / -div);
        cur %= div;
    }
    while (res.size > 1 && res.digits[res.size] == 0) res.pop();
    return res;
}

BigInteger BigInteger::operator/ (const BigInteger& x) const {
    static std::vector<BigInteger> pow2 = {1};
    static std::vector<BigInteger> estimate;
    estimate.clear();
    if (*this < x) return 0;
    BigInteger cur = x;
    while (cur <= *this) {
        estimate.emplace_back(cur), cur += cur;
        if (estimate.size() > pow2.size()) pow2.emplace_back(pow2.back() + pow2.back());
    }
    if (cur == *this) {
        pow2.back().flag = !(flag ^ x.flag);
        return BigInteger(pow2.back());
    }
    BigInteger res = pow2[estimate.size() - 1];
    cur = estimate.back();
    for (long i = estimate.size() - 1; i >= 0; i--) {
        if (cur + estimate[i] <= *this) cur += estimate[i], res += pow2[i];
    }
    res.flag = !(flag ^ x.flag);
    return res;
}

BigInteger BigInteger::operator% (const long long& x) const {
    if (x == 2) return digits[1] & 1;
    return *this - (*this / x * x);
} 
BigInteger BigInteger::operator% (const BigInteger& x) const {
    return *this - (*this / x * x);
} 

BigInteger BigInteger::pow(const long long& x) const {
    BigInteger res = 1, a = *this;
    for (long long t = x; t != 0; t >>= 1) {
        if (t & 1) res *= a;
        a *= a;
    }
    return res;
}
BigInteger BigInteger::pow(const long long& x, const BigInteger& p) const {
    BigInteger res = 1, a = *this % p;
    for (long long t = x; t != 0; t >>= 1) {
        if (t & 1) res = res * a % p;
        a = a * a % p;
    }
    return res;
}

BigInteger BigInteger::sqrt(const long long& x) const {
    BigInteger l = 0, r = 1;
    while (r.pow(x) <= *this) l = r, r += r;
    while (l + 1 < r) {
        BigInteger mid = (l + r) / 2;
        if (mid.pow(x) <= *this) l = mid;
        else r = mid;
    }
    return l.pow(x) <= *this ? l : r;
}

BigInteger& BigInteger::operator+= (const BigInteger& x) {return *this = *this + x;}
BigInteger& BigInteger::operator-= (const BigInteger& x) {return *this = *this - x;}
BigInteger& BigInteger::operator*= (const BigInteger& x) {return *this = *this * x;}
BigInteger& BigInteger::operator/= (const long long& x) {return *this = *this / x;}
BigInteger& BigInteger::operator/= (const BigInteger& x) {return *this = *this / x;}
BigInteger& BigInteger::operator%= (const long long& x) {return *this = *this / x;}
BigInteger& BigInteger::operator%= (const BigInteger& x) {return *this = *this % x;}

#endif //BIGINTEGER_H

然后该怎么写就怎么写，把类型名换成 BigInteger 就行了

by JjHh @ 2024-05-25 13:00:44

@hhy517090 谢谢已经AC了