2 条题解
-
0
使用封装好的大整数模板
#include<bits/stdc++.h> using namespace std; struct BigIntTiny { int sign; std::vector<int> v; BigIntTiny() : sign(1) {} BigIntTiny(const std::string &s) { *this = s; } BigIntTiny(int v) { char buf[21]; sprintf(buf, "%d", v); *this = buf; } void zip(int unzip) { if (unzip == 0) { for (int i = 0; i < (int)v.size(); i++) v[i] = get_pos(i * 4) + get_pos(i * 4 + 1) * 10 + get_pos(i * 4 + 2) * 100 + get_pos(i * 4 + 3) * 1000; } else for (int i = (v.resize(v.size() * 4), (int)v.size() - 1), a; i >= 0; i--) a = (i % 4 >= 2) ? v[i / 4] / 100 : v[i / 4] % 100, v[i] = (i & 1) ? a / 10 : a % 10; setsign(1, 1); } int get_pos(unsigned pos) const { return pos >= v.size() ? 0 : v[pos]; } BigIntTiny &setsign(int newsign, int rev) { for (int i = (int)v.size() - 1; i > 0 && v[i] == 0; i--) v.erase(v.begin() + i); sign = (v.size() == 0 || (v.size() == 1 && v[0] == 0)) ? 1 : (rev ? newsign * sign : newsign); return *this; } std::string to_str() const { BigIntTiny b = *this; std::string s; for (int i = (b.zip(1), 0); i < (int)b.v.size(); ++i) s += char(*(b.v.rbegin() + i) + '0'); return (sign < 0 ? "-" : "") + (s.empty() ? std::string("0") : s); } bool absless(const BigIntTiny &b) const { if (v.size() != b.v.size()) return v.size() < b.v.size(); for (int i = (int)v.size() - 1; i >= 0; i--) if (v[i] != b.v[i]) return v[i] < b.v[i]; return false; } BigIntTiny operator-() const { BigIntTiny c = *this; c.sign = (v.size() > 1 || v[0]) ? -c.sign : 1; return c; } BigIntTiny &operator=(const std::string &s) { if (s[0] == '-') *this = s.substr(1); else { for (int i = (v.clear(), 0); i < (int)s.size(); ++i) v.push_back(*(s.rbegin() + i) - '0'); zip(0); } return setsign(s[0] == '-' ? -1 : 1, sign = 1); } bool operator<(const BigIntTiny &b) const { return sign != b.sign ? sign < b.sign : (sign == 1 ? absless(b) : b.absless(*this)); } bool operator==(const BigIntTiny &b) const { return v == b.v && sign == b.sign; } BigIntTiny &operator+=(const BigIntTiny &b) { if (sign != b.sign) return *this = (*this) - -b; v.resize(std::max(v.size(), b.v.size()) + 1); for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++) { carry += v[i] + b.get_pos(i); v[i] = carry % 10000, carry /= 10000; } return setsign(sign, 0); } BigIntTiny operator+(const BigIntTiny &b) const { BigIntTiny c = *this; return c += b; } void add_mul(const BigIntTiny &b, int mul) { v.resize(std::max(v.size(), b.v.size()) + 2); for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++) { carry += v[i] + b.get_pos(i) * mul; v[i] = carry % 10000, carry /= 10000; } } BigIntTiny operator-(const BigIntTiny &b) const { if (sign != b.sign) return (*this) + -b; if (absless(b)) return -(b - *this); BigIntTiny c; for (int i = 0, borrow = 0; i < (int)v.size(); i++) { borrow += v[i] - b.get_pos(i); c.v.push_back(borrow); c.v.back() -= 10000 * (borrow >>= 31); } return c.setsign(sign, 0); } BigIntTiny operator*(const BigIntTiny &b) const { if (b < *this) return b * *this; BigIntTiny c, d = b; for (int i = 0; i < (int)v.size(); i++, d.v.insert(d.v.begin(), 0)) c.add_mul(d, v[i]); return c.setsign(sign * b.sign, 0); } BigIntTiny operator/(const BigIntTiny &b) const { BigIntTiny c, d; d.v.resize(v.size()); double db = 1.0 / (b.v.back() + (b.get_pos((unsigned)b.v.size() - 2) / 1e4) + (b.get_pos((unsigned)b.v.size() - 3) + 1) / 1e8); for (int i = (int)v.size() - 1; i >= 0; i--) { c.v.insert(c.v.begin(), v[i]); int m = (int)((c.get_pos((int)b.v.size()) * 10000 + c.get_pos((int)b.v.size() - 1)) * db); c = c - b * m, d.v[i] += m; while (!(c < b)) c = c - b, d.v[i] += 1; } return d.setsign(sign * b.sign, 0); } BigIntTiny operator%(const BigIntTiny &b) const { return *this - *this / b * b; } bool operator>(const BigIntTiny &b) const { return b < *this; } bool operator<=(const BigIntTiny &b) const { return !(b < *this); } bool operator>=(const BigIntTiny &b) const { return !(*this < b); } bool operator!=(const BigIntTiny &b) const { return !(*this == b); } }; int main(){ int n; cin >> n; BigIntTiny sum = 0; BigIntTiny now = 1; for(int i = 1; i <= n; i++) { now = now * i; sum += now; } cout << sum.to_str(); return 0; }
-
0
#include <bits/stdc++.h> using namespace std; const int LEN = 50 * 2 + 50; int n; int aLen, sLen; int a[LEN + 5], s[LEN + 5]; int main() { cin >> n; // 构建高精度的 0! 以及高精度的 0 aLen = 1; a[0] = 1; sLen = 1; s[0] = 0; // n 次,每次算出 i!,然后累加进 s for (int i = 1; i <= n; i++) { // 【计算 i!】 for (int j = 0; j < aLen; j++) a[j] *= i; for (int j = 0; j < aLen - 1; j++) { a[j + 1] += a[j] / 10; a[j] %= 10; } while (a[aLen - 1] > 9) { a[aLen] = a[aLen - 1] / 10; a[aLen - 1] %= 10; aLen++; } // 【s += i!】 sLen = max(sLen, aLen); for (int i = 0; i < sLen; i++) s[i] += a[i]; for (int j = 0; j < sLen - 1; j++) { s[j + 1] += s[j] / 10; s[j] %= 10; } while (s[aLen - 1] > 9) { s[sLen] = a[sLen - 1] / 10; s[sLen - 1] %= 10; sLen++; } } // 输出 for (int i = sLen - 1; i >= 0; i--) cout << s[i]; return 0; }
- 1
信息
- ID
- 13413
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 12
- 已通过
- 7
- 上传者