当前位置: 首页 > news >正文

学习笔记:压位高精

考虑 10-base 高精度,单次运算复杂度为 \(O(\log_{10}V)\)。使用 10-base 的主要原因是 std::to_string 很方便、输出也很简单。

但效率太低。实际上,一般打高精度都是 1e4-base,或更激进地,1e9-base。

注意高精乘低精是 \(O(len)\) 而非 \(O(len^2)\)

需要考虑输出。由于用的是 10-power 作为 base,所以只需要把每四位直接输出即可。注意除首位外需要补前导 0 直到四位。

struct BI {std::vector<int> s;BI() {}BI(int x) {for (; x; s.push_back(x % 10000), x /= 10000);return;}BI& operator= (int q) {return *this = (BI)q;}bool operator> (const BI &q) {if (s.size() != q.s.size())return s.size() > q.s.size();for (int i = (int)s.size() - 1; ~i; --i)if (s[i] != q.s[i])return s[i] > q.s[i];return 0;}BI operator* (int q) const {int lx = s.size();std::vector<long long> res(lx + 3);for (int i = 0; i < lx; ++i)res[i] = (long long)s[i] * q;BI p;for (int j = 0; j < lx + 2; ++j)res[j + 1] += res[j] / 10000, res[j] %= 10000;int len = lx + 2;for (; ~len && !res[len]; --len);for (int j = 0; j <= len; ++j)p.s.push_back(res[j]);return p;}void out(void) {for (int i = (int)s.size() - 1; ~i; --i) {auto p = std::to_string(s[i]);if (i != (int)s.size() - 1)for (; (int)p.size() < 4; p = "0" + p);std::cout << p;}std::cout << '\n';return;}
};
http://www.hskmm.com/?act=detail&tid=23671

相关文章:

  • 吉司机 + 历史和练习
  • 近期杂题,怎么重名了
  • vp 记录 edu 181
  • 状压 DP
  • 近期杂题
  • 学习笔记:分拆数与 Ferrers 图
  • DDP 与全局平衡二叉树
  • 并查集 D. Shark [Codeforces Round 484(Div. 2)]
  • 实用指南:Spark核心技术解析:从RDD到Dataset的演进与实践
  • 随笔0
  • 加密算法基本原理、特点及采用场景
  • Hackersdaddy ROUGE CTF 2025 完整解题记录
  • AI元人文系列:透明推理者——下一代大模型架构设计
  • 个人随笔
  • 实用指南:1、docker入门简介
  • 调试parlant的大模型配置,最终自己动手写了g4f的模块挂载 - 教程
  • PowerShell注意点
  • 太极 - MKT
  • 题解:P12410 「知りたくなかった、失うのなら」
  • unity面向组合开发二:EC的代码实践
  • 《咳咳,未来编程大师,顶尖程序员的第一条博客》
  • CSP-JF36
  • 超越炒作:使用Agentic AI构建系统架构
  • K个节点的组内逆序调整
  • 【任务】自然语言处理——情感分析 <上>
  • 文件目录
  • 【Azure App Service】Root CA on App Service
  • QOJ #8147. Math Exam 题解
  • 10.03模拟赛t3
  • 国庆梦熊集训做题记录